sdk/python/arvados/_ranges.py

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