sdk/python/arvados/_ranges.py

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