sdk/python/arvados/ranges.py

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