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(dl.locator, "range_start", range_start, "block_start", block_start, "range_end", range_end, "block_end", block_end)
 100         if range_end <= block_start:
 101             # range ends before this block starts, so don't look at any more locators
 102             break
 103
 104         if range_start >= block_start and range_end <= block_end:
 105             # range starts and ends in this block
 106             resp.append(LocatorAndRange(dl.locator, block_size, dl.segment_offset + (range_start - block_start), range_size))
 107         elif range_start >= block_start and range_end > block_end:
 108             # range starts in this block
 109             resp.append(LocatorAndRange(dl.locator, block_size, dl.segment_offset + (range_start - block_start), block_end - range_start))
 110         elif range_start < block_start and range_end > block_end:
 111             # range starts in a previous block and extends to further blocks
 112             resp.append(LocatorAndRange(dl.locator, block_size, dl.segment_offset, block_size))
 113         elif range_start < block_start and range_end <= block_end:
 114             # range starts in a previous block and ends in this block
 115             resp.append(LocatorAndRange(dl.locator, block_size, dl.segment_offset, range_end - block_start))
 116         block_start = block_end
 117         i += 1
 118     return resp
 119
 120 def replace_range(data_locators, new_range_start, new_range_size, new_locator, new_segment_offset):
 121     """
 122     Replace a file segment range with a new segment.
 123
 124     NOTE::
 125     data_locators will be updated in place
 126
 127     :data_locators:
 128       list of Range objects, assumes that segments are in order and contiguous
 129
 130     :new_range_start:
 131       start of range to replace in data_locators
 132
 133     :new_range_size:
 134       size of range to replace in data_locators
 135
 136     :new_locator:
 137       locator for new segment to be inserted
 138
 139     :new_segment_offset:
 140       segment offset within the locator
 141
 142     """
 143     if new_range_size == 0:
 144         return
 145
 146     new_range_end = new_range_start + new_range_size
 147
 148     if len(data_locators) == 0:
 149         data_locators.append(Range(new_locator, new_range_start, new_range_size, new_segment_offset))
 150         return
 151
 152     last = data_locators[-1]
 153     if (last.range_start+last.range_size) == new_range_start:
 154         if last.locator == new_locator:
 155             # extend last segment
 156             last.range_size += new_range_size
 157         else:
 158             data_locators.append(Range(new_locator, new_range_start, new_range_size, new_segment_offset))
 159         return
 160
 161     i = first_block(data_locators, new_range_start, new_range_size)
 162     if i is None:
 163         return
 164
 165     # We should always start at the first segment due to the binary
 166     # search.
 167     while i < len(data_locators):
 168         dl = data_locators[i]
 169         old_segment_start = dl.range_start
 170         old_segment_end = old_segment_start + dl.range_size
 171         _logger.debug(dl, "range_start", new_range_start, "segment_start", old_segment_start, "range_end", new_range_end, "segment_end", old_segment_end)
 172         if new_range_end <= old_segment_start:
 173             # range ends before this segment starts, so don't look at any more locators
 174             break
 175
 176         if  old_segment_start <= new_range_start and new_range_end <= old_segment_end:
 177             # new range starts and ends in old segment
 178             # split segment into up to 3 pieces
 179             if (new_range_start-old_segment_start) > 0:
 180                 data_locators[i] = Range(dl.locator, old_segment_start, (new_range_start-old_segment_start), dl.segment_offset)
 181                 data_locators.insert(i+1, Range(new_locator, new_range_start, new_range_size, new_segment_offset))
 182             else:
 183                 data_locators[i] = Range(new_locator, new_range_start, new_range_size, new_segment_offset)
 184                 i -= 1
 185             if (old_segment_end-new_range_end) > 0:
 186                 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))
 187             return
 188         elif old_segment_start <= new_range_start and new_range_end > old_segment_end:
 189             # range starts in this segment
 190             # split segment into 2 pieces
 191             data_locators[i] = Range(dl.locator, old_segment_start, (new_range_start-old_segment_start), dl.segment_offset)
 192             data_locators.insert(i+1, Range(new_locator, new_range_start, new_range_size, new_segment_offset))
 193             i += 1
 194         elif new_range_start < old_segment_start and new_range_end >= old_segment_end:
 195             # range starts in a previous segment and extends to further segments
 196             # delete this segment
 197             del data_locators[i]
 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 ends in this segment
 201             # move the starting point of this segment up, and shrink it.
 202             data_locators[i] = Range(dl.locator, new_range_end, (old_segment_end-new_range_end), dl.segment_offset + (new_range_end-old_segment_start))
 203             return
 204         i += 1