sdk/python/arvados/ranges.py

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