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(\"%s\", %i, %i, %i)" % (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 contigious, 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(\"%s\", %i, %i, %i)" % (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 the range and return list of LocatorAndRange
  70     objects.
  71
  72     :data_locators:
  73       list of Range objects, assumes that blocks are in order and contigous
  74
  75     :range_start:
  76       start of range
  77
  78     :range_size:
  79       size of range
  80
  81     '''
  82     if range_size == 0:
  83         return []
  84     resp = []
  85     range_start = long(range_start)
  86     range_size = long(range_size)
  87     range_end = range_start + range_size
  88
  89     i = first_block(data_locators, range_start, range_size)
  90     if i is None:
  91         return []
  92
  93     while i < len(data_locators):
  94         dl = data_locators[i]
  95         block_start = dl.range_start
  96         block_size = dl.range_size
  97         block_end = block_start + block_size
  98         _logger.debug(dl.locator, "range_start", range_start, "block_start", block_start, "range_end", range_end, "block_end", block_end)
  99         if range_end <= block_start:
 100             # range ends before this block starts, so don't look at any more locators
 101             break
 102
 103         #if range_start >= block_end:
 104             # Range starts after this block ends, so go to next block.
 105             # We should always start at the first block due to the binary
 106             # search above, so this test is unnecessary but useful to help
 107             # document the algorithm.
 108             #next
 109
 110         if range_start >= block_start and range_end <= block_end:
 111             # range starts and ends in this block
 112             resp.append(LocatorAndRange(dl.locator, block_size, dl.segment_offset + (range_start - block_start), range_size))
 113         elif range_start >= block_start and range_end > block_end:
 114             # range starts in this block
 115             resp.append(LocatorAndRange(dl.locator, block_size, dl.segment_offset + (range_start - block_start), block_end - range_start))
 116         elif range_start < block_start and range_end > block_end:
 117             # range starts in a previous block and extends to further blocks
 118             resp.append(LocatorAndRange(dl.locator, block_size, dl.segment_offset, block_size))
 119         elif range_start < block_start and range_end <= block_end:
 120             # range starts in a previous block and ends in this block
 121             resp.append(LocatorAndRange(dl.locator, block_size, dl.segment_offset, range_end - block_start))
 122         block_start = block_end
 123         i += 1
 124     return resp
 125
 126 def replace_range(data_locators, new_range_start, new_range_size, new_locator, new_segment_offset):
 127     '''
 128     Replace a file segment range with a new segment.
 129
 130     NOTE::
 131     data_locators will be updated in place
 132
 133     :data_locators:
 134       list of Range objects, assumes that segments are in order and contigous
 135
 136     :new_range_start:
 137       start of range to replace in data_locators
 138
 139     :new_range_size:
 140       size of range to replace in data_locators
 141
 142     :new_locator:
 143       locator for new segment to be inserted
 144
 145     :new_segment_offset:
 146       segment offset within the locator
 147
 148     '''
 149     if new_range_size == 0:
 150         return
 151
 152     new_range_start = long(new_range_start)
 153     new_range_size = long(new_range_size)
 154     new_range_end = new_range_start + new_range_size
 155
 156     if len(data_locators) == 0:
 157         data_locators.append(Range(new_locator, new_range_start, new_range_size, new_segment_offset))
 158         return
 159
 160     last = data_locators[-1]
 161     if (last.range_start+last.range_size) == new_range_start:
 162         if last.locator == new_locator:
 163             # extend last segment
 164             last.range_size += new_range_size
 165         else:
 166             data_locators.append(Range(new_locator, new_range_start, new_range_size, new_segment_offset))
 167         return
 168
 169     i = first_block(data_locators, new_range_start, new_range_size)
 170     if i is None:
 171         return
 172
 173     while i < len(data_locators):
 174         dl = data_locators[i]
 175         old_segment_start = dl.range_start
 176         old_segment_end = old_segment_start + dl.range_size
 177         _logger.debug(dl, "range_start", new_range_start, "segment_start", old_segment_start, "range_end", new_range_end, "segment_end", old_segment_end)
 178         if new_range_end <= old_segment_start:
 179             # range ends before this segment starts, so don't look at any more locators
 180             break
 181
 182         #if range_start >= old_segment_end:
 183             # Range starts after this segment ends, so go to next segment.
 184             # We should always start at the first segment due to the binary
 185             # search above, so this test is unnecessary but useful to help
 186             # document the algorithm.
 187             #next
 188
 189         if  old_segment_start <= new_range_start and new_range_end <= old_segment_end:
 190             # new range starts and ends in old segment
 191             # split segment into up to 3 pieces
 192             if (new_range_start-old_segment_start) > 0:
 193                 data_locators[i] = Range(dl.locator, old_segment_start, (new_range_start-old_segment_start), dl.segment_offset)
 194                 data_locators.insert(i+1, Range(new_locator, new_range_start, new_range_size, new_segment_offset))
 195             else:
 196                 data_locators[i] = Range(new_locator, new_range_start, new_range_size, new_segment_offset)
 197                 i -= 1
 198             if (old_segment_end-new_range_end) > 0:
 199                 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))
 200             return
 201         elif old_segment_start <= new_range_start and new_range_end > old_segment_end:
 202             # range starts in this segment
 203             # split segment into 2 pieces
 204             data_locators[i] = Range(dl.locator, old_segment_start, (new_range_start-old_segment_start), dl.segment_offset)
 205             data_locators.insert(i+1, Range(new_locator, new_range_start, new_range_size, new_segment_offset))
 206             i += 1
 207         elif new_range_start < old_segment_start and new_range_end >= old_segment_end:
 208             # range starts in a previous segment and extends to further segments
 209             # delete this segment
 210             del data_locators[i]
 211             i -= 1
 212         elif new_range_start < old_segment_start and new_range_end < old_segment_end:
 213             # range starts in a previous segment and ends in this segment
 214             # move the starting point of this segment up, and shrink it.
 215             data_locators[i] = Range(dl.locator, new_range_end, (old_segment_end-new_range_end), dl.segment_offset + (new_range_end-old_segment_start))
 216             return
 217         i += 1