here's another bug bandaid this one got through the 3rd flush
# block tree structure
# blocks written to are leaves # depth is log2 leaves # when a flush is made, all blocks are written, and also enough nodes such that every leaf can be accessed within depth lookups. # consider we have an existing tree # with say m flushes, containing n leaves (or m leaves). we'll likely call it n. # each flush shows which leaves it has # additionally, with the final flush, each leaf has an existing depth. # when we reflush, we need to provide a new index for any leaves that become too deep. # which leaves are too deep? # we could basically walk them all to find out. this would be a consistent first approach. class Simple: class Chunk: def __init__(self, offset, data): self.start = offset self.data = data self.end = self.start + len(self.data) class Flush: # flush has a list of new leaves, and a list of indexes to old leaves with ranges def __init__(self, *writes, prev_flush=None): self.prev_flush = prev_flush self.data = writes # find extents start = min((write.start for write in self.data)) end = max((write.end for write in self.data)) if prev_flush is None: self.start = start self.end = end self.index = [] return self.start = min(start, prev_flush.start) self.end = max(end, prev_flush.end) self.index = [Simple.Chunk(prev_flush.start, prev_flush)] # find leaf count and leaf depths #offset = start #while offset < end: def __len__(self): return self.end - self.start #def lookup(self, offset def leaves(self, start = None, end = None, depth = 0): if start is None: start = self.start if end is None: end = self.end print('leaves', depth, self, start, end) offset = start data_iter = iter(self.data) index_iter = iter(self.index) next_write = next(data_iter, None) next_index = next(index_iter, None) while offset < end: if next_write is not None and offset >= next_write.start: # offset >= next_write # so we look in the write substart = offset - next_write.start subend = min(end, next_write.end) - next_write.start print('yielding', depth, self, offset, subend + next_write.start) yield (depth, offset, next_write.data[substart:subend]) offset += subend - substart assert offset <= end next_write = next(data_iter, None) else: # offset < next_write # so we look in the index assert next_index is not None subend = min(next_write.start, end) if next_write is not None else end while offset >= next_index.end: next_index = next(index_iter) assert offset >= next_index.start and offset < next_index.end subend = min(subend, next_index.end) assert subend <= end yield from next_index.data.leaves(offset, subend, depth + 1) offset = subend assert offset <= end if end == self.end: assert next(index_iter, None) is None def __init__(self, latest = None): self.tip = latest self.pending = [] def write(self, offset, data): for idx, pending in [*enumerate(self.pending)]: if pending.start <= offset + len(data) and pending.end >= offset: # merge pending with data # then merge pending with neighbors # so, algorithm could simplify to inserting in a sorted manner, and then merging neighbors, except we want to ensure that this data replaces old data merged_data = pending.data[:offset - pending.start] + data + pending.data[offset + len(data) - pending.start:] # we could maybe merge 'merged' via recursion # basically we'd excise pending, and then write merged self.pending.pop(idx) return self.write(min(offset, pending.start), merged_data) elif pending.start > offset + len(data): # passed this data without overlap return self.pending.insert(idx, self.Chunk(offset, data)) self.pending.append(self.Chunk(offset, data)) def flush(self): self.tip = self.Flush(*self.pending, prev_flush=self.tip) self.pending = [] def leaves(self, start = None, end = None): if self.tip is not None: return self.tip.leaves(start, end) if __name__ == '__main__': import random SIZE=4096 store = Simple() comparison = bytearray(SIZE) store.write(0, bytes(SIZE)) for flushes in range(1024): for writes in range(1): start = random.randint(0, SIZE) end = random.randint(0, SIZE) start, end = (start, end) if start <= end else (end, start) data = random.randbytes(end - start) comparison[start:end] = data store.write(start, data) store.flush() last_offset = 0 max_depth = 0 for depth, offset, data in store.leaves(): assert offset >= last_offset assert comparison[last_offset:offset] == bytes(offset - last_offset) last_offset = offset + len(data) assert comparison[offset:last_offset] == data max_depth = max(depth, max_depth) assert comparison[last_offset:] == bytes(len(comparison) - last_offset) print(flushes, max_depth, 'OK')