Обратное построение дерева (с нечетным количеством детей)

Question

Я только что узнал о сервисе AWS Glacier и хотел написать небольшое приложение на Python для загрузки файлов через REST API. Я посмотрел на требуемые заголовки и наткнулся на x-amz-sha256-tree-hash, Мне нужно вычислить хэш SHA-256 для всего файла, а также хэш родительского элемента для всех хешей каждого блока размером 1 МБ. Это приводит к следующему дереву:

(Изображение взято отсюда)

Я уже сделал функцию, которая читает блоки размером 1 МБ, и класс, который вычисляет их хэши на лету, но потом я полностью борюсь:

В моем приложении я сделал класс под названием chunk который берет данные и вычисляет хеш в __init__ метод, а также содержит родительские и дочерние элементы (как обычное дерево). Когда пользователь открывает файл, эти экземпляры чанков будут сгенерированы правильно с соответствующими им хешами (в этом примере это будет 7 экземпляров чанков).

Теперь у меня есть две большие проблемы, которые связаны друг с другом:

1. Как мне построить это дерево в обратном порядке? В основном мне нужно создать новый чанк для каждых двух экземпляров чанка на нижнем слое и вычислить хеш на основе этих двух хешей. Но где мне хранить этого родителя? У детей родительский и есть ли обратная прогулка по дереву?
2. Как это работает с нечетным количеством детей? Если у меня есть алгоритм, который проходит через каждый родительский слой, я бы пропустил последний (0,5 МБ) блок.

Я проверил эту тему на SO, но этот метод работает только с четным количеством детей, что не всегда дается.

Можете ли вы помочь мне найти способ / алгоритм / подход к решению этой проблемы?

Заранее спасибо!

Павел

Answer 1

Сначала рассчитайте количество уровней, затем

def proclevel(levels):
    if levels > 0:
        generator = proclevel(levels - 1)
        temp = None
        for firsthash, secondhash in generator:
            if not temp: temp = hashofthem(firsthash, secondhash)
            else: yield temp, hashofthem(firsthash, secondhash); temp = None
        #If odd number of packets
        if temp: yield temp, None
    else:
        temp = None
        for chunk in chunks:
            if not temp: temp = hash(chunk)
            else: yield temp, hash(chunk); temp = None
        if temp: yield temp, None

Убедитесь, что обрабатывает None как второй аргумент в hashofthem:)