sdk/python/arvados/_ranges.py

   1 from __future__ import division
   2 from builtins import object
   3 import logging
   4
   5 _logger = logging.getLogger('arvados.ranges')
   6
   7 # Log level below 'debug' !
   8 RANGES_SPAM = 9
   9
  10 class Range(object):
  11     __slots__ = ("locator", "range_start", "range_size", "segment_offset")
  12
  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
  18
  19     def __repr__(self):
  20         return "Range(%r, %r, %r, %r)" % (self.locator, self.range_start, self.range_size, self.segment_offset)
  21
  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)
  27
  28 def first_block(data_locators, range_start):
  29     block_start = 0
  30
  31     # range_start/block_start is the inclusive lower bound
  32     # range_end/block_end is the exclusive upper bound
  33
  34     hi = len(data_locators)
  35     lo = 0
  36     i = (hi + lo) // 2
  37     block_size = data_locators[i].range_size
  38     block_start = data_locators[i].range_start
  39     block_end = block_start + block_size
  40
  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):
  45         if lo == i:
  46             # must be out of range, fail
  47             return None
  48         if range_start > block_start:
  49             lo = i
  50         else:
  51             hi = i
  52         i = (hi + lo) // 2
  53         block_size = data_locators[i].range_size
  54         block_start = data_locators[i].range_start
  55         block_end = block_start + block_size
  56
  57     return i
  58
  59 class LocatorAndRange(object):
  60     __slots__ = ("locator", "block_size", "segment_offset", "segment_size")
  61
  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
  67
  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)
  73
  74     def __repr__(self):
  75         return "LocatorAndRange(%r, %r, %r, %r)" % (self.locator, self.block_size, self.segment_offset, self.segment_size)
  76
  77 def locators_and_ranges(data_locators, range_start, range_size, limit=None):
  78     """Get blocks that are covered by a range.
  79
  80     Returns a list of LocatorAndRange objects.
  81
  82     :data_locators:
  83       list of Range objects, assumes that blocks are in order and contiguous
  84
  85     :range_start:
  86       start of range
  87
  88     :range_size:
  89       size of range
  90
  91     :limit:
  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
  94       limit.
  95
  96     """
  97     if range_size == 0:
  98         return []
  99     resp = []
 100     range_end = range_start + range_size
 101
 102     i = first_block(data_locators, range_start)
 103     if i is None:
 104         return []
 105
 106     # We should always start at the first segment due to the binary
 107     # search.
 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
 118             break
 119
 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
 133         i += 1
 134     return resp
 135
 136 def replace_range(data_locators, new_range_start, new_range_size, new_locator, new_segment_offset):
 137     """
 138     Replace a file segment range with a new segment.
 139
 140     NOTE::
 141     data_locators will be updated in place
 142
 143     :data_locators:
 144       list of Range objects, assumes that segments are in order and contiguous
 145
 146     :new_range_start:
 147       start of range to replace in data_locators
 148
 149     :new_range_size:
 150       size of range to replace in data_locators
 151
 152     :new_locator:
 153       locator for new segment to be inserted
 154
 155     :new_segment_offset:
 156       segment offset within the locator
 157
 158     """
 159     if new_range_size == 0:
 160         return
 161
 162     new_range_end = new_range_start + new_range_size
 163
 164     if len(data_locators) == 0:
 165         data_locators.append(Range(new_locator, new_range_start, new_range_size, new_segment_offset))
 166         return
 167
 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
 173         else:
 174             data_locators.append(Range(new_locator, new_range_start, new_range_size, new_segment_offset))
 175         return
 176
 177     i = first_block(data_locators, new_range_start)
 178     if i is None:
 179         return
 180
 181     # We should always start at the first segment due to the binary
 182     # search.
 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,
 190             old_segment_end)
 191         if new_range_end <= old_segment_start:
 192             # range ends before this segment starts, so don't look at any more locators
 193             break
 194
 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))
 201             else:
 202                 data_locators[i] = Range(new_locator, new_range_start, new_range_size, new_segment_offset)
 203                 i -= 1
 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))
 206             return
 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))
 212             i += 1
 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
 216             del data_locators[i]
 217             i -= 1
 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))
 222             return
 223         i += 1