sdk/python/arvados/ranges.py

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