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