+
+ # range_start/block_start is the inclusive lower bound
+ # range_end/block_end is the exclusive upper bound
+
+ hi = len(data_locators)
+ lo = 0
+ i = int((hi + lo) / 2)
+ block_size = data_locators[i][BLOCKSIZE]
+ block_start = data_locators[i][OFFSET]
+ block_end = block_start + block_size
+ if debug: print '---'
+
+ # perform a binary search for the first block
+ # assumes that all of the blocks are contigious, so range_start is guaranteed
+ # to either fall into the range of a block or be outside the block range entirely
+ while not (range_start >= block_start and range_start < block_end):
+ if lo == i:
+ # must be out of range, fail
+ return []
+ if range_start > block_start:
+ lo = i
+ else:
+ hi = i
+ i = int((hi + lo) / 2)
+ if debug: print lo, i, hi
+ block_size = data_locators[i][BLOCKSIZE]
+ block_start = data_locators[i][OFFSET]
+ block_end = block_start + block_size
+
+ while i < len(data_locators):
+ locator, block_size, block_start = data_locators[i]