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