Ideone.com

fork download

copy

#ifndef STORAGE_H
#define STORAGE_H
 
#include <algorithm>
#include <string>
#include <stack> 
#include <vector>
#include <utility>
#include <chrono>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
 
using namespace std;
using namespace chrono;
 
typedef struct tree_s tree_t;
typedef struct node_s node_t;
typedef struct data_s data_t;
 
struct data_s {
    string key;
    string val;
};
 
struct node_s {    
    data_t data;
 
    uint64_t weight; // количество узлов у данного узла
 
    node_t *left;
    node_t *right;
 
    node_t *parent;
};
 
struct tree_s
{
    node_t *root; // указатель на корень дерева
};
 
class bntree
{    
public:
    bntree();
    ~bntree();
 
    // Вставка данных, ключ - значение
    void insert(string key, string val = "");
    // Удаление узла по индексу
    void erase(uint64_t index);
    // Удаление узла по ключу
    void erase(string key);
    // Взятие узла по индексу
    data_t *get(uint64_t index);
    // Взятие узла по ключу
    data_t *get(string key);
 
    // Поиск узла по ключу, возвращает индекс узла
    uint64_t search(string key);
 
    // Кол-во элементов в дереве
    uint64_t size();
 
    // Печать дерева
    void print();
 
private:    
    tree_t *tree;
 
    uint64_t get_child_weight(node_t *node);
    node_t *node_new();
    void node_free(node_t *e);
 
    bool erase_simple(node_t *search_node);
 
    void clear(node_t *p);
 
    void print(node_t *p, int indent);
 
    void balance(node_t *p);
 
public:
    // Ближайшая степень 2-ки к числу
    uint64_t cpl2(uint64_t x);
 
    // Быстрый логарифм
    long ilog2(long x);
 
    // Вес узла к глубине
    uint64_t weight_to_depth(node_t *p);
};
 
#endif
 
bntree::bntree() {
    this->tree = new tree_t();
}
 
bntree::~bntree() {
    this->clear(this->tree->root);
    delete this->tree->root;
}
 
node_t *bntree::node_new() {
    return new node_t();
}
 
void bntree::node_free(node_t *n) {
    delete n;
}
 
void bntree::clear(node_t *p) {
    if (p != NULL) {
        if (p->right) {
            this->clear(p->right);
            this->node_free(p->right);
        }
 
        if (p->left) {
            this->clear(p->left);
            this->node_free(p->left);
        }
    }
}
 
uint64_t bntree::search(string key) {
    if (!this->tree->root) {
        return -1;
    }
 
    node_t *search_node = this->tree->root;
    uint64_t index_node = this->get_child_weight(search_node->left);
 
    for (;;) {
        if (key == search_node->data.key) {
            return index_node; // найден узел с таким ключем, вернем его индекс
        } else if (key > search_node->data.key) {
            search_node = search_node->right;
 
            if (search_node == NULL)
                return -1;
 
            index_node += (this->get_child_weight(search_node->left) + 1);
        } else {
            search_node = search_node->left;
 
            if (search_node == NULL)
                return -1;
 
            index_node -= (this->get_child_weight(search_node->left) + 1);
        }
    }
}
 
void bntree::insert(string key, string val) {
    node_t *search_node, *prev_node, **node;
 
    node = &this->tree->root;
    search_node = this->tree->root;
    prev_node = NULL;
    uint64_t index_node;
 
    if (!this->tree->root) {
        index_node = 0;
    } else {
        index_node = this->get_child_weight(search_node->left);
    }
 
    uint64_t index_del = -1;
 
    for (;;) {
 
        if (search_node == NULL) {
            // Добавялем узел
            search_node = *node = this->node_new();
 
            search_node->data.key = key;
            search_node->data.val = val;
            search_node->weight = 1; // новый узел имеет вес 1
 
            search_node->left = search_node->right = NULL;
            search_node->parent = prev_node;
 
            break;
        } else if (key > search_node->data.key) {
            // Идем направо
            prev_node = search_node;
            search_node->weight++; // увеличиваем вес узла
            node = &search_node->right;
            search_node = search_node->right;
 
            if (search_node)
                index_node += (this->get_child_weight(search_node->left) + 1);
 
        } else if (key < search_node->data.key) {
            // Идем налево
            prev_node = search_node;
            search_node->weight++; // увеличиваем вес узла
            node = &search_node->left;
            search_node = search_node->left;
 
            if (search_node)
                index_node -= (this->get_child_weight(search_node->left) + 1);
        } else {
            // Если такой ключ уже существует, то обновляем значение.
            search_node->data.val = val;
 
            // Идем назад и отменяем изменение веса у верхних узлов
            for (;;) {
 
                if (search_node->parent) {
                    search_node = search_node->parent;
                } else {
                    return;
                }
 
                search_node->weight--;
            }
        }
    }
 
    this->balance(search_node);
 
    return;
}
 
bool bntree::erase_simple(node_t *search_node) {
 
    node_t *prev_node = search_node->parent;
 
    if (!search_node->left && !search_node->right) {
        // Удаляемый узел является листом.
 
        // Обнуляем соответствующую ссылку родителя.
        if (prev_node == NULL) {
            // Удаляемый узел корень.
            this->tree->root = NULL;
        } else if (prev_node->left == search_node) {
            prev_node->left = NULL;
        } else if (prev_node->right == search_node) {
            prev_node->right = NULL;
        }
 
    } else if (search_node->left && !search_node->right) {
        // Удаляемый узел имеет только левого ребенка.
 
        // Перекомпануем ссылки родителя на левого внука.
        if (prev_node == NULL) {
            // Удаляемый узел корень.
            this->tree->root = search_node->left;
            this->tree->root->parent = NULL;
        } else if (prev_node->left == search_node) {
            prev_node->left = search_node->left;
            search_node->left->parent = prev_node;
        } else if (prev_node->right == search_node) {
            prev_node->right = search_node->left;
            search_node->left->parent = prev_node;
        }
 
    } else if (!search_node->left && search_node->right) {
        // Удаляемый узел имеет только правого ребенка.
 
        // Перекомпануем ссылки родителя на правого внука.
        if (prev_node == NULL) {
            // Удаляемый узел корень.
            this->tree->root = search_node->right;
            this->tree->root->parent = NULL;
        } else if (prev_node->left == search_node) {
            prev_node->left = search_node->right;
            search_node->right->parent = prev_node;
        } else if (prev_node->right == search_node) {
            prev_node->right = search_node->right;
            search_node->right->parent = prev_node;
        }
 
    } else {
        // Удаляемый узел имеет двух детей. Здесь не обрабатываем.
 
        return false;
    }
 
    return true;
}
 
void bntree::erase(uint64_t index) {
 
    if (index < 0 || index > this->size() - 1) {
        return;
    }
 
    node_t *search_node = this->tree->root;
    uint64_t index_node = this->get_child_weight(search_node->left);
 
    for (;;) {
        if (index == index_node) {
            if (this->erase_simple(search_node)) {
                // pass
            } else if (search_node->left && search_node->right) {
                // Самый сложный случай, удаляемый узел имеет 2-х детей.
 
                node_t *del_node = search_node;
                uint64_t _index;
                // Маленькая балансировка, если правый вес больше левого то удаляем через право
                // иначе через лево
                if (search_node->right->weight > search_node->left->weight) {
                    _index = index_node + 1;
                } else {
                    _index = index_node - 1;
                }
 
                // Ищем узел со следующим индексом.
                for (;;) {
                    if (_index == index_node) {
                        // Узел найден
                        break;
                    } else if (_index > index_node) {
                        search_node->weight--;
                        search_node = search_node->right;
                        index_node += (this->get_child_weight(search_node->left) + 1);
                    } else {
                        search_node->weight--;
                        search_node = search_node->left;
                        index_node -= (this->get_child_weight(search_node->right) + 1);
                    }
                }
 
                del_node->data = search_node->data;
                this->erase_simple(search_node);
            }
 
            this->node_free(search_node);
 
            return;
        } else if (index > index_node) {
            search_node->weight--;
            search_node = search_node->right;
            index_node += (this->get_child_weight(search_node->left) + 1);
        } else {
            search_node->weight--;
            search_node = search_node->left;
            index_node -= (this->get_child_weight(search_node->right) + 1);
        }
    }
}
 
void bntree::erase(string key) {
 
    node_t *search_node = this->tree->root;
    uint64_t index_node = this->get_child_weight(search_node->left);
 
    for (;;) {
        if (key == search_node->data.key) {
            if (this->erase_simple(search_node)) {
                // pass
            } else if (search_node->left && search_node->right) {
                // Самый сложный случай, удаляемый узел имеет 2-х детей.
 
                node_t *del_node = search_node;
                uint64_t _index;
                // Маленькая балансировка, если правый вес больше левого то удаляем через право
                // иначе через лево
                if (search_node->right->weight > search_node->left->weight) {
                    _index = index_node + 1;
                } else {
                    _index = index_node - 1;
                }
 
                // Ищем узел со следующим индексом.
                for (;;) {
                    if (_index == index_node) {
                        // Узел найден
                        break;
                    } else if (_index > index_node) {
                        search_node->weight--;
                        search_node = search_node->right;
                        index_node += (this->get_child_weight(search_node->left) + 1);
                    } else {
                        search_node->weight--;
 
                        search_node = search_node->left;
                        index_node -= (this->get_child_weight(search_node->right) + 1);
                    }
                }
 
                del_node->data = search_node->data;
                this->erase_simple(search_node);
            }
 
            this->node_free(search_node);
 
            return;
        } else if (key > search_node->data.key) {
            search_node->weight--;
            search_node = search_node->right;
            index_node += (this->get_child_weight(search_node->left) + 1);
        } else {
            search_node->weight--;
            search_node = search_node->left;
            index_node -= (this->get_child_weight(search_node->right) + 1);
        }
 
    }
}
 
uint64_t bntree::get_child_weight(node_t *node) {
    if (node) {
        return node->weight;
    }
 
    return 0;
}
 
data_t *bntree::get(uint64_t index) {
    if (index < 0 || index > this->size() - 1) {
        return NULL;
    }
 
    node_t *search_node = this->tree->root;
    uint64_t index_node = this->get_child_weight(search_node->left);
 
    for (;;) {
        if (index == index_node) {
            return &search_node->data;
        } else if (index > index_node) {
            search_node = search_node->right;
            index_node += (this->get_child_weight(search_node->left) + 1);
        } else {
            search_node = search_node->left;
            index_node -= (this->get_child_weight(search_node->right) + 1);
        }
    }
}
 
data_t *bntree::get(string key) {
    node_t *search_node = this->tree->root;
    uint64_t index_node = this->get_child_weight(search_node->left);
 
    for (;;) {
        if (key == search_node->data.key) {
            return &search_node->data;
        } else if (key > search_node->data.key) {
            search_node = search_node->right;
            index_node += (this->get_child_weight(search_node->left) + 1);
        } else {
            search_node = search_node->left;
            index_node -= (this->get_child_weight(search_node->right) + 1);
        }
    }
 
    return NULL;
}
 
uint64_t bntree::size() {
    if (this->tree->root) {
        return this->tree->root->weight;
    }
 
    return 0;
}
 
void bntree::print() {
    this->print(this->tree->root, 5);
}
 
void bntree::print(node_t *p, int indent) {
    if (p != NULL) {
        if (p->right) {
            this->print(p->right, indent + 4);
        }
        if (indent) {
            //std::cout << std::setw(indent) << ' ' << p->weight << ' ';
            std::cout << std::setw(indent) << ' ';
        }
        if (p->right) {
            std::cout << " /\n" << std::setw(indent) << ' ';
        }
        //std::cout << p->data.key << ":" << p->data.val << "\n ";
        std::cout << p->data.key << ":" << p << ":" << p->parent << "\n ";
        if (p->left) {
            std::cout << std::setw(indent) << ' ' << " \\\n";
            this->print(p->left, indent + 4);
        }
    }
}
 
/*
 * Балансировка поворотом
 * Балансировка делается на основе весов левого и правого поддерева
 */
void bntree::balance(node_t *p) {
    if (!p) {
        return;
    }
 
    node_t *child = NULL;
    node_t *parent = NULL;
    uint64_t ld = 0;
    uint64_t rd = 0;
 
    for (;;) {
        ld = this->weight_to_depth(p->left);
        rd = this->weight_to_depth(p->right);
 
        if (ld > rd && ld - rd > 1) {
            // Правый поворот. 
            // Глубина левого поддерева больше, чем глубина правого
 
            child = p->left;
            parent = p->parent;
 
            if (parent) {
                if (parent->right == p) {
                    parent->right = child;
                } else if (parent->left == p) {
                    parent->left = child;
                }
            } else {
                this->tree->root = child;
            }
            child->parent = parent;
            p->parent = child;
 
            p->left = child->right;
            if (p->left) {
                p->left->parent = p;
            }
 
            child->right = p;
 
            p->weight = 1 + this->get_child_weight(p->left) + this->get_child_weight(p->right);
            child->weight = 1 + this->get_child_weight(child->left) + this->get_child_weight(child->right);
 
            //p = child;
            break;
        } else if (rd > ld && rd - ld > 1) {
            // Левый поворот. 
            // Глубина правого поддерева больше, чем глубина левого
 
            child = p->right;
            parent = p->parent;
 
            if (parent) {
                if (parent->right == p) {
                    parent->right = child;
                } else if (parent->left == p) {
                    parent->left = child;
                }
            } else {
                this->tree->root = child;
            }
            child->parent = parent;
            p->parent = child;
 
            p->right = child->left;
            if (p->right) {
                p->right->parent = p;
            }
 
            child->left = p;
 
            p->weight = 1 + this->get_child_weight(p->left) + this->get_child_weight(p->right);
            child->weight = 1 + this->get_child_weight(child->left) + this->get_child_weight(child->right);
 
            //p = child;
            break;
        }
 
        if (p->parent) {
            p = p->parent;
        } else {
            break;
        }
    }
 
    return;
}
 
/*
 * Возвращает первое число в степени 2, которое больше или ровно x
 */
uint64_t bntree::cpl2(uint64_t x) {
    x = x - 1;
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
    x = x | (x >> 32);
 
    return x + 1;
}
 
/*
 * Двоичный логарифм от числа
 */
long bntree::ilog2(long d) {
    int result;
    std::frexp(d, &result);
    return result - 1;
}
 
/*
 * Вес к глубине
 */
uint64_t bntree::weight_to_depth(node_t *p) {
    if (p == NULL) {
        return 0;
    }
 
    if (p->weight == 1) {
        return 1;
    } else if (p->weight == 2) {
        return 2;
    }
 
    return this->ilog2(this->cpl2(p->weight));
}
 
int main(void){
  bntree tree;
  int arr[13] = {8, 4, 30, 2, 6, 10, 36, 9, 12,38, 13, 14, 15 };
  for(int i=0; i<13; i++) {
     string zero_padded = std::to_string(arr[i]*0.000001).substr(4); 
     tree.insert(zero_padded);
  }
  tree.print();
}

I2lmbmRlZiBTVE9SQUdFX0gKI2RlZmluZSBTVE9SQUdFX0gKCiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDxzdGFjaz4gCiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDx1dGlsaXR5PgojaW5jbHVkZSA8Y2hyb25vPgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxmc3RyZWFtPgojaW5jbHVkZSA8aW9tYW5pcD4KI2luY2x1ZGUgPGNtYXRoPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdXNpbmcgbmFtZXNwYWNlIGNocm9ubzsKCnR5cGVkZWYgc3RydWN0IHRyZWVfcyB0cmVlX3Q7CnR5cGVkZWYgc3RydWN0IG5vZGVfcyBub2RlX3Q7CnR5cGVkZWYgc3RydWN0IGRhdGFfcyBkYXRhX3Q7CiAgICAKc3RydWN0IGRhdGFfcyB7CiAgICBzdHJpbmcga2V5OwogICAgc3RyaW5nIHZhbDsKfTsKCnN0cnVjdCBub2RlX3MgeyAgICAKICAgIGRhdGFfdCBkYXRhOwogICAgCiAgICB1aW50NjRfdCB3ZWlnaHQ7IC8vINC60L7Qu9C40YfQtdGB0YLQstC+INGD0LfQu9C+0LIg0YMg0LTQsNC90L3QvtCz0L4g0YPQt9C70LAKICAgIAogICAgbm9kZV90ICpsZWZ0OwogICAgbm9kZV90ICpyaWdodDsKICAgIAogICAgbm9kZV90ICpwYXJlbnQ7Cn07CgpzdHJ1Y3QgdHJlZV9zCnsKICAgIG5vZGVfdCAqcm9vdDsgLy8g0YPQutCw0LfQsNGC0LXQu9GMINC90LAg0LrQvtGA0LXQvdGMINC00LXRgNC10LLQsAp9OwoKY2xhc3MgYm50cmVlCnsgICAgCnB1YmxpYzoKICAgIGJudHJlZSgpOwogICAgfmJudHJlZSgpOwogICAgCiAgICAvLyDQktGB0YLQsNCy0LrQsCDQtNCw0L3QvdGL0YUsINC60LvRjtGHIC0g0LfQvdCw0YfQtdC90LjQtQogICAgdm9pZCBpbnNlcnQoc3RyaW5nIGtleSwgc3RyaW5nIHZhbCA9ICIiKTsKICAgIC8vINCj0LTQsNC70LXQvdC40LUg0YPQt9C70LAg0L/QviDQuNC90LTQtdC60YHRgwogICAgdm9pZCBlcmFzZSh1aW50NjRfdCBpbmRleCk7CiAgICAvLyDQo9C00LDQu9C10L3QuNC1INGD0LfQu9CwINC/0L4g0LrQu9GO0YfRgwogICAgdm9pZCBlcmFzZShzdHJpbmcga2V5KTsKICAgIC8vINCS0LfRj9GC0LjQtSDRg9C30LvQsCDQv9C+INC40L3QtNC10LrRgdGDCiAgICBkYXRhX3QgKmdldCh1aW50NjRfdCBpbmRleCk7CiAgICAvLyDQktC30Y/RgtC40LUg0YPQt9C70LAg0L/QviDQutC70Y7Rh9GDCiAgICBkYXRhX3QgKmdldChzdHJpbmcga2V5KTsKICAgIAogICAgLy8g0J/QvtC40YHQuiDRg9C30LvQsCDQv9C+INC60LvRjtGH0YMsINCy0L7Qt9Cy0YDQsNGJ0LDQtdGCINC40L3QtNC10LrRgSDRg9C30LvQsAogICAgdWludDY0X3Qgc2VhcmNoKHN0cmluZyBrZXkpOwogICAgCiAgICAvLyDQmtC+0Lst0LLQviDRjdC70LXQvNC10L3RgtC+0LIg0LIg0LTQtdGA0LXQstC1CiAgICB1aW50NjRfdCBzaXplKCk7CiAgICAKICAgIC8vINCf0LXRh9Cw0YLRjCDQtNC10YDQtdCy0LAKICAgIHZvaWQgcHJpbnQoKTsKICAgIApwcml2YXRlOiAgICAKICAgIHRyZWVfdCAqdHJlZTsKICAgIAogICAgdWludDY0X3QgZ2V0X2NoaWxkX3dlaWdodChub2RlX3QgKm5vZGUpOwogICAgbm9kZV90ICpub2RlX25ldygpOwogICAgdm9pZCBub2RlX2ZyZWUobm9kZV90ICplKTsKICAgIAogICAgYm9vbCBlcmFzZV9zaW1wbGUobm9kZV90ICpzZWFyY2hfbm9kZSk7CiAgICAKICAgIHZvaWQgY2xlYXIobm9kZV90ICpwKTsKICAgIAogICAgdm9pZCBwcmludChub2RlX3QgKnAsIGludCBpbmRlbnQpOwoKICAgIHZvaWQgYmFsYW5jZShub2RlX3QgKnApOwogICAgCnB1YmxpYzoKICAgIC8vINCR0LvQuNC20LDQudGI0LDRjyDRgdGC0LXQv9C10L3RjCAyLdC60Lgg0Log0YfQuNGB0LvRgwogICAgdWludDY0X3QgY3BsMih1aW50NjRfdCB4KTsKICAgIAogICAgLy8g0JHRi9GB0YLRgNGL0Lkg0LvQvtCz0LDRgNC40YTQvAogICAgbG9uZyBpbG9nMihsb25nIHgpOwogICAgCiAgICAvLyDQktC10YEg0YPQt9C70LAg0Log0LPQu9GD0LHQuNC90LUKICAgIHVpbnQ2NF90IHdlaWdodF90b19kZXB0aChub2RlX3QgKnApOwp9OwoKI2VuZGlmCgpibnRyZWU6OmJudHJlZSgpIHsKICAgIHRoaXMtPnRyZWUgPSBuZXcgdHJlZV90KCk7Cn0KCmJudHJlZTo6fmJudHJlZSgpIHsKICAgIHRoaXMtPmNsZWFyKHRoaXMtPnRyZWUtPnJvb3QpOwogICAgZGVsZXRlIHRoaXMtPnRyZWUtPnJvb3Q7Cn0KCm5vZGVfdCAqYm50cmVlOjpub2RlX25ldygpIHsKICAgIHJldHVybiBuZXcgbm9kZV90KCk7Cn0KCnZvaWQgYm50cmVlOjpub2RlX2ZyZWUobm9kZV90ICpuKSB7CiAgICBkZWxldGUgbjsKfQoKdm9pZCBibnRyZWU6OmNsZWFyKG5vZGVfdCAqcCkgewogICAgaWYgKHAgIT0gTlVMTCkgewogICAgICAgIGlmIChwLT5yaWdodCkgewogICAgICAgICAgICB0aGlzLT5jbGVhcihwLT5yaWdodCk7CiAgICAgICAgICAgIHRoaXMtPm5vZGVfZnJlZShwLT5yaWdodCk7CiAgICAgICAgfQoKICAgICAgICBpZiAocC0+bGVmdCkgewogICAgICAgICAgICB0aGlzLT5jbGVhcihwLT5sZWZ0KTsKICAgICAgICAgICAgdGhpcy0+bm9kZV9mcmVlKHAtPmxlZnQpOwogICAgICAgIH0KICAgIH0KfQoKdWludDY0X3QgYm50cmVlOjpzZWFyY2goc3RyaW5nIGtleSkgewogICAgaWYgKCF0aGlzLT50cmVlLT5yb290KSB7CiAgICAgICAgcmV0dXJuIC0xOwogICAgfQoKICAgIG5vZGVfdCAqc2VhcmNoX25vZGUgPSB0aGlzLT50cmVlLT5yb290OwogICAgdWludDY0X3QgaW5kZXhfbm9kZSA9IHRoaXMtPmdldF9jaGlsZF93ZWlnaHQoc2VhcmNoX25vZGUtPmxlZnQpOwoKICAgIGZvciAoOzspIHsKICAgICAgICBpZiAoa2V5ID09IHNlYXJjaF9ub2RlLT5kYXRhLmtleSkgewogICAgICAgICAgICByZXR1cm4gaW5kZXhfbm9kZTsgLy8g0L3QsNC50LTQtdC9INGD0LfQtdC7INGBINGC0LDQutC40Lwg0LrQu9GO0YfQtdC8LCDQstC10YDQvdC10Lwg0LXQs9C+INC40L3QtNC10LrRgQogICAgICAgIH0gZWxzZSBpZiAoa2V5ID4gc2VhcmNoX25vZGUtPmRhdGEua2V5KSB7CiAgICAgICAgICAgIHNlYXJjaF9ub2RlID0gc2VhcmNoX25vZGUtPnJpZ2h0OwoKICAgICAgICAgICAgaWYgKHNlYXJjaF9ub2RlID09IE5VTEwpCiAgICAgICAgICAgICAgICByZXR1cm4gLTE7CgogICAgICAgICAgICBpbmRleF9ub2RlICs9ICh0aGlzLT5nZXRfY2hpbGRfd2VpZ2h0KHNlYXJjaF9ub2RlLT5sZWZ0KSArIDEpOwogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIHNlYXJjaF9ub2RlID0gc2VhcmNoX25vZGUtPmxlZnQ7CgogICAgICAgICAgICBpZiAoc2VhcmNoX25vZGUgPT0gTlVMTCkKICAgICAgICAgICAgICAgIHJldHVybiAtMTsKCiAgICAgICAgICAgIGluZGV4X25vZGUgLT0gKHRoaXMtPmdldF9jaGlsZF93ZWlnaHQoc2VhcmNoX25vZGUtPmxlZnQpICsgMSk7CiAgICAgICAgfQogICAgfQp9Cgp2b2lkIGJudHJlZTo6aW5zZXJ0KHN0cmluZyBrZXksIHN0cmluZyB2YWwpIHsKICAgIG5vZGVfdCAqc2VhcmNoX25vZGUsICpwcmV2X25vZGUsICoqbm9kZTsKCiAgICBub2RlID0gJnRoaXMtPnRyZWUtPnJvb3Q7CiAgICBzZWFyY2hfbm9kZSA9IHRoaXMtPnRyZWUtPnJvb3Q7CiAgICBwcmV2X25vZGUgPSBOVUxMOwogICAgdWludDY0X3QgaW5kZXhfbm9kZTsKCiAgICBpZiAoIXRoaXMtPnRyZWUtPnJvb3QpIHsKICAgICAgICBpbmRleF9ub2RlID0gMDsKICAgIH0gZWxzZSB7CiAgICAgICAgaW5kZXhfbm9kZSA9IHRoaXMtPmdldF9jaGlsZF93ZWlnaHQoc2VhcmNoX25vZGUtPmxlZnQpOwogICAgfQoKICAgIHVpbnQ2NF90IGluZGV4X2RlbCA9IC0xOwoKICAgIGZvciAoOzspIHsKCiAgICAgICAgaWYgKHNlYXJjaF9ub2RlID09IE5VTEwpIHsKICAgICAgICAgICAgLy8g0JTQvtCx0LDQstGP0LvQtdC8INGD0LfQtdC7CiAgICAgICAgICAgIHNlYXJjaF9ub2RlID0gKm5vZGUgPSB0aGlzLT5ub2RlX25ldygpOwoKICAgICAgICAgICAgc2VhcmNoX25vZGUtPmRhdGEua2V5ID0ga2V5OwogICAgICAgICAgICBzZWFyY2hfbm9kZS0+ZGF0YS52YWwgPSB2YWw7CiAgICAgICAgICAgIHNlYXJjaF9ub2RlLT53ZWlnaHQgPSAxOyAvLyDQvdC+0LLRi9C5INGD0LfQtdC7INC40LzQtdC10YIg0LLQtdGBIDEKCiAgICAgICAgICAgIHNlYXJjaF9ub2RlLT5sZWZ0ID0gc2VhcmNoX25vZGUtPnJpZ2h0ID0gTlVMTDsKICAgICAgICAgICAgc2VhcmNoX25vZGUtPnBhcmVudCA9IHByZXZfbm9kZTsKCiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIH0gZWxzZSBpZiAoa2V5ID4gc2VhcmNoX25vZGUtPmRhdGEua2V5KSB7CiAgICAgICAgICAgIC8vINCY0LTQtdC8INC90LDQv9GA0LDQstC+CiAgICAgICAgICAgIHByZXZfbm9kZSA9IHNlYXJjaF9ub2RlOwogICAgICAgICAgICBzZWFyY2hfbm9kZS0+d2VpZ2h0Kys7IC8vINGD0LLQtdC70LjRh9C40LLQsNC10Lwg0LLQtdGBINGD0LfQu9CwCiAgICAgICAgICAgIG5vZGUgPSAmc2VhcmNoX25vZGUtPnJpZ2h0OwogICAgICAgICAgICBzZWFyY2hfbm9kZSA9IHNlYXJjaF9ub2RlLT5yaWdodDsKCiAgICAgICAgICAgIGlmIChzZWFyY2hfbm9kZSkKICAgICAgICAgICAgICAgIGluZGV4X25vZGUgKz0gKHRoaXMtPmdldF9jaGlsZF93ZWlnaHQoc2VhcmNoX25vZGUtPmxlZnQpICsgMSk7CgogICAgICAgIH0gZWxzZSBpZiAoa2V5IDwgc2VhcmNoX25vZGUtPmRhdGEua2V5KSB7CiAgICAgICAgICAgIC8vINCY0LTQtdC8INC90LDQu9C10LLQvgogICAgICAgICAgICBwcmV2X25vZGUgPSBzZWFyY2hfbm9kZTsKICAgICAgICAgICAgc2VhcmNoX25vZGUtPndlaWdodCsrOyAvLyDRg9Cy0LXQu9C40YfQuNCy0LDQtdC8INCy0LXRgSDRg9C30LvQsAogICAgICAgICAgICBub2RlID0gJnNlYXJjaF9ub2RlLT5sZWZ0OwogICAgICAgICAgICBzZWFyY2hfbm9kZSA9IHNlYXJjaF9ub2RlLT5sZWZ0OwoKICAgICAgICAgICAgaWYgKHNlYXJjaF9ub2RlKQogICAgICAgICAgICAgICAgaW5kZXhfbm9kZSAtPSAodGhpcy0+Z2V0X2NoaWxkX3dlaWdodChzZWFyY2hfbm9kZS0+bGVmdCkgKyAxKTsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAvLyDQldGB0LvQuCDRgtCw0LrQvtC5INC60LvRjtGHINGD0LbQtSDRgdGD0YnQtdGB0YLQstGD0LXRgiwg0YLQviDQvtCx0L3QvtCy0LvRj9C10Lwg0LfQvdCw0YfQtdC90LjQtS4KICAgICAgICAgICAgc2VhcmNoX25vZGUtPmRhdGEudmFsID0gdmFsOwoKICAgICAgICAgICAgLy8g0JjQtNC10Lwg0L3QsNC30LDQtCDQuCDQvtGC0LzQtdC90Y/QtdC8INC40LfQvNC10L3QtdC90LjQtSDQstC10YHQsCDRgyDQstC10YDRhdC90LjRhSDRg9C30LvQvtCyCiAgICAgICAgICAgIGZvciAoOzspIHsKCiAgICAgICAgICAgICAgICBpZiAoc2VhcmNoX25vZGUtPnBhcmVudCkgewogICAgICAgICAgICAgICAgICAgIHNlYXJjaF9ub2RlID0gc2VhcmNoX25vZGUtPnBhcmVudDsKICAgICAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICAgICAgcmV0dXJuOwogICAgICAgICAgICAgICAgfQoKICAgICAgICAgICAgICAgIHNlYXJjaF9ub2RlLT53ZWlnaHQtLTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KCiAgICB0aGlzLT5iYWxhbmNlKHNlYXJjaF9ub2RlKTsKCiAgICByZXR1cm47Cn0KCmJvb2wgYm50cmVlOjplcmFzZV9zaW1wbGUobm9kZV90ICpzZWFyY2hfbm9kZSkgewoKICAgIG5vZGVfdCAqcHJldl9ub2RlID0gc2VhcmNoX25vZGUtPnBhcmVudDsKCiAgICBpZiAoIXNlYXJjaF9ub2RlLT5sZWZ0ICYmICFzZWFyY2hfbm9kZS0+cmlnaHQpIHsKICAgICAgICAvLyDQo9C00LDQu9GP0LXQvNGL0Lkg0YPQt9C10Lsg0Y/QstC70Y/QtdGC0YHRjyDQu9C40YHRgtC+0LwuCgogICAgICAgIC8vINCe0LHQvdGD0LvRj9C10Lwg0YHQvtC+0YLQstC10YLRgdGC0LLRg9GO0YnRg9GOINGB0YHRi9C70LrRgyDRgNC+0LTQuNGC0LXQu9GPLgogICAgICAgIGlmIChwcmV2X25vZGUgPT0gTlVMTCkgewogICAgICAgICAgICAvLyDQo9C00LDQu9GP0LXQvNGL0Lkg0YPQt9C10Lsg0LrQvtGA0LXQvdGMLgogICAgICAgICAgICB0aGlzLT50cmVlLT5yb290ID0gTlVMTDsKICAgICAgICB9IGVsc2UgaWYgKHByZXZfbm9kZS0+bGVmdCA9PSBzZWFyY2hfbm9kZSkgewogICAgICAgICAgICBwcmV2X25vZGUtPmxlZnQgPSBOVUxMOwogICAgICAgIH0gZWxzZSBpZiAocHJldl9ub2RlLT5yaWdodCA9PSBzZWFyY2hfbm9kZSkgewogICAgICAgICAgICBwcmV2X25vZGUtPnJpZ2h0ID0gTlVMTDsKICAgICAgICB9CgogICAgfSBlbHNlIGlmIChzZWFyY2hfbm9kZS0+bGVmdCAmJiAhc2VhcmNoX25vZGUtPnJpZ2h0KSB7CiAgICAgICAgLy8g0KPQtNCw0LvRj9C10LzRi9C5INGD0LfQtdC7INC40LzQtdC10YIg0YLQvtC70YzQutC+INC70LXQstC+0LPQviDRgNC10LHQtdC90LrQsC4KCiAgICAgICAgLy8g0J/QtdGA0LXQutC+0LzQv9Cw0L3Rg9C10Lwg0YHRgdGL0LvQutC4INGA0L7QtNC40YLQtdC70Y8g0L3QsCDQu9C10LLQvtCz0L4g0LLQvdGD0LrQsC4KICAgICAgICBpZiAocHJldl9ub2RlID09IE5VTEwpIHsKICAgICAgICAgICAgLy8g0KPQtNCw0LvRj9C10LzRi9C5INGD0LfQtdC7INC60L7RgNC10L3RjC4KICAgICAgICAgICAgdGhpcy0+dHJlZS0+cm9vdCA9IHNlYXJjaF9ub2RlLT5sZWZ0OwogICAgICAgICAgICB0aGlzLT50cmVlLT5yb290LT5wYXJlbnQgPSBOVUxMOwogICAgICAgIH0gZWxzZSBpZiAocHJldl9ub2RlLT5sZWZ0ID09IHNlYXJjaF9ub2RlKSB7CiAgICAgICAgICAgIHByZXZfbm9kZS0+bGVmdCA9IHNlYXJjaF9ub2RlLT5sZWZ0OwogICAgICAgICAgICBzZWFyY2hfbm9kZS0+bGVmdC0+cGFyZW50ID0gcHJldl9ub2RlOwogICAgICAgIH0gZWxzZSBpZiAocHJldl9ub2RlLT5yaWdodCA9PSBzZWFyY2hfbm9kZSkgewogICAgICAgICAgICBwcmV2X25vZGUtPnJpZ2h0ID0gc2VhcmNoX25vZGUtPmxlZnQ7CiAgICAgICAgICAgIHNlYXJjaF9ub2RlLT5sZWZ0LT5wYXJlbnQgPSBwcmV2X25vZGU7CiAgICAgICAgfQoKICAgIH0gZWxzZSBpZiAoIXNlYXJjaF9ub2RlLT5sZWZ0ICYmIHNlYXJjaF9ub2RlLT5yaWdodCkgewogICAgICAgIC8vINCj0LTQsNC70Y/QtdC80YvQuSDRg9C30LXQuyDQuNC80LXQtdGCINGC0L7Qu9GM0LrQviDQv9GA0LDQstC+0LPQviDRgNC10LHQtdC90LrQsC4KCiAgICAgICAgLy8g0J/QtdGA0LXQutC+0LzQv9Cw0L3Rg9C10Lwg0YHRgdGL0LvQutC4INGA0L7QtNC40YLQtdC70Y8g0L3QsCDQv9GA0LDQstC+0LPQviDQstC90YPQutCwLgogICAgICAgIGlmIChwcmV2X25vZGUgPT0gTlVMTCkgewogICAgICAgICAgICAvLyDQo9C00LDQu9GP0LXQvNGL0Lkg0YPQt9C10Lsg0LrQvtGA0LXQvdGMLgogICAgICAgICAgICB0aGlzLT50cmVlLT5yb290ID0gc2VhcmNoX25vZGUtPnJpZ2h0OwogICAgICAgICAgICB0aGlzLT50cmVlLT5yb290LT5wYXJlbnQgPSBOVUxMOwogICAgICAgIH0gZWxzZSBpZiAocHJldl9ub2RlLT5sZWZ0ID09IHNlYXJjaF9ub2RlKSB7CiAgICAgICAgICAgIHByZXZfbm9kZS0+bGVmdCA9IHNlYXJjaF9ub2RlLT5yaWdodDsKICAgICAgICAgICAgc2VhcmNoX25vZGUtPnJpZ2h0LT5wYXJlbnQgPSBwcmV2X25vZGU7CiAgICAgICAgfSBlbHNlIGlmIChwcmV2X25vZGUtPnJpZ2h0ID09IHNlYXJjaF9ub2RlKSB7CiAgICAgICAgICAgIHByZXZfbm9kZS0+cmlnaHQgPSBzZWFyY2hfbm9kZS0+cmlnaHQ7CiAgICAgICAgICAgIHNlYXJjaF9ub2RlLT5yaWdodC0+cGFyZW50ID0gcHJldl9ub2RlOwogICAgICAgIH0KCiAgICB9IGVsc2UgewogICAgICAgIC8vINCj0LTQsNC70Y/QtdC80YvQuSDRg9C30LXQuyDQuNC80LXQtdGCINC00LLRg9GFINC00LXRgtC10LkuINCX0LTQtdGB0Ywg0L3QtSDQvtCx0YDQsNCx0LDRgtGL0LLQsNC10LwuCgogICAgICAgIHJldHVybiBmYWxzZTsKICAgIH0KCiAgICByZXR1cm4gdHJ1ZTsKfQoKdm9pZCBibnRyZWU6OmVyYXNlKHVpbnQ2NF90IGluZGV4KSB7CgogICAgaWYgKGluZGV4IDwgMCB8fCBpbmRleCA+IHRoaXMtPnNpemUoKSAtIDEpIHsKICAgICAgICByZXR1cm47CiAgICB9CgogICAgbm9kZV90ICpzZWFyY2hfbm9kZSA9IHRoaXMtPnRyZWUtPnJvb3Q7CiAgICB1aW50NjRfdCBpbmRleF9ub2RlID0gdGhpcy0+Z2V0X2NoaWxkX3dlaWdodChzZWFyY2hfbm9kZS0+bGVmdCk7CgogICAgZm9yICg7OykgewogICAgICAgIGlmIChpbmRleCA9PSBpbmRleF9ub2RlKSB7CiAgICAgICAgICAgIGlmICh0aGlzLT5lcmFzZV9zaW1wbGUoc2VhcmNoX25vZGUpKSB7CiAgICAgICAgICAgICAgICAvLyBwYXNzCiAgICAgICAgICAgIH0gZWxzZSBpZiAoc2VhcmNoX25vZGUtPmxlZnQgJiYgc2VhcmNoX25vZGUtPnJpZ2h0KSB7CiAgICAgICAgICAgICAgICAvLyDQodCw0LzRi9C5INGB0LvQvtC20L3Ri9C5INGB0LvRg9GH0LDQuSwg0YPQtNCw0LvRj9C10LzRi9C5INGD0LfQtdC7INC40LzQtdC10YIgMi3RhSDQtNC10YLQtdC5LgoKICAgICAgICAgICAgICAgIG5vZGVfdCAqZGVsX25vZGUgPSBzZWFyY2hfbm9kZTsKICAgICAgICAgICAgICAgIHVpbnQ2NF90IF9pbmRleDsKICAgICAgICAgICAgICAgIC8vINCc0LDQu9C10L3RjNC60LDRjyDQsdCw0LvQsNC90YHQuNGA0L7QstC60LAsINC10YHQu9C4INC/0YDQsNCy0YvQuSDQstC10YEg0LHQvtC70YzRiNC1INC70LXQstC+0LPQviDRgtC+INGD0LTQsNC70Y/QtdC8INGH0LXRgNC10Lcg0L/RgNCw0LLQvgogICAgICAgICAgICAgICAgLy8g0LjQvdCw0YfQtSDRh9C10YDQtdC3INC70LXQstC+CiAgICAgICAgICAgICAgICBpZiAoc2VhcmNoX25vZGUtPnJpZ2h0LT53ZWlnaHQgPiBzZWFyY2hfbm9kZS0+bGVmdC0+d2VpZ2h0KSB7CiAgICAgICAgICAgICAgICAgICAgX2luZGV4ID0gaW5kZXhfbm9kZSArIDE7CiAgICAgICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgICAgIF9pbmRleCA9IGluZGV4X25vZGUgLSAxOwogICAgICAgICAgICAgICAgfQoKICAgICAgICAgICAgICAgIC8vINCY0YnQtdC8INGD0LfQtdC7INGB0L4g0YHQu9C10LTRg9GO0YnQuNC8INC40L3QtNC10LrRgdC+0LwuCiAgICAgICAgICAgICAgICBmb3IgKDs7KSB7CiAgICAgICAgICAgICAgICAgICAgaWYgKF9pbmRleCA9PSBpbmRleF9ub2RlKSB7CiAgICAgICAgICAgICAgICAgICAgICAgIC8vINCj0LfQtdC7INC90LDQudC00LXQvQogICAgICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgICAgICB9IGVsc2UgaWYgKF9pbmRleCA+IGluZGV4X25vZGUpIHsKICAgICAgICAgICAgICAgICAgICAgICAgc2VhcmNoX25vZGUtPndlaWdodC0tOwogICAgICAgICAgICAgICAgICAgICAgICBzZWFyY2hfbm9kZSA9IHNlYXJjaF9ub2RlLT5yaWdodDsKICAgICAgICAgICAgICAgICAgICAgICAgaW5kZXhfbm9kZSArPSAodGhpcy0+Z2V0X2NoaWxkX3dlaWdodChzZWFyY2hfbm9kZS0+bGVmdCkgKyAxKTsKICAgICAgICAgICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgICAgICAgICBzZWFyY2hfbm9kZS0+d2VpZ2h0LS07CiAgICAgICAgICAgICAgICAgICAgICAgIHNlYXJjaF9ub2RlID0gc2VhcmNoX25vZGUtPmxlZnQ7CiAgICAgICAgICAgICAgICAgICAgICAgIGluZGV4X25vZGUgLT0gKHRoaXMtPmdldF9jaGlsZF93ZWlnaHQoc2VhcmNoX25vZGUtPnJpZ2h0KSArIDEpOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICBkZWxfbm9kZS0+ZGF0YSA9IHNlYXJjaF9ub2RlLT5kYXRhOwogICAgICAgICAgICAgICAgdGhpcy0+ZXJhc2Vfc2ltcGxlKHNlYXJjaF9ub2RlKTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgdGhpcy0+bm9kZV9mcmVlKHNlYXJjaF9ub2RlKTsKCiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9IGVsc2UgaWYgKGluZGV4ID4gaW5kZXhfbm9kZSkgewogICAgICAgICAgICBzZWFyY2hfbm9kZS0+d2VpZ2h0LS07CiAgICAgICAgICAgIHNlYXJjaF9ub2RlID0gc2VhcmNoX25vZGUtPnJpZ2h0OwogICAgICAgICAgICBpbmRleF9ub2RlICs9ICh0aGlzLT5nZXRfY2hpbGRfd2VpZ2h0KHNlYXJjaF9ub2RlLT5sZWZ0KSArIDEpOwogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIHNlYXJjaF9ub2RlLT53ZWlnaHQtLTsKICAgICAgICAgICAgc2VhcmNoX25vZGUgPSBzZWFyY2hfbm9kZS0+bGVmdDsKICAgICAgICAgICAgaW5kZXhfbm9kZSAtPSAodGhpcy0+Z2V0X2NoaWxkX3dlaWdodChzZWFyY2hfbm9kZS0+cmlnaHQpICsgMSk7CiAgICAgICAgfQogICAgfQp9Cgp2b2lkIGJudHJlZTo6ZXJhc2Uoc3RyaW5nIGtleSkgewoKICAgIG5vZGVfdCAqc2VhcmNoX25vZGUgPSB0aGlzLT50cmVlLT5yb290OwogICAgdWludDY0X3QgaW5kZXhfbm9kZSA9IHRoaXMtPmdldF9jaGlsZF93ZWlnaHQoc2VhcmNoX25vZGUtPmxlZnQpOwoKICAgIGZvciAoOzspIHsKICAgICAgICBpZiAoa2V5ID09IHNlYXJjaF9ub2RlLT5kYXRhLmtleSkgewogICAgICAgICAgICBpZiAodGhpcy0+ZXJhc2Vfc2ltcGxlKHNlYXJjaF9ub2RlKSkgewogICAgICAgICAgICAgICAgLy8gcGFzcwogICAgICAgICAgICB9IGVsc2UgaWYgKHNlYXJjaF9ub2RlLT5sZWZ0ICYmIHNlYXJjaF9ub2RlLT5yaWdodCkgewogICAgICAgICAgICAgICAgLy8g0KHQsNC80YvQuSDRgdC70L7QttC90YvQuSDRgdC70YPRh9Cw0LksINGD0LTQsNC70Y/QtdC80YvQuSDRg9C30LXQuyDQuNC80LXQtdGCIDIt0YUg0LTQtdGC0LXQuS4KICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgbm9kZV90ICpkZWxfbm9kZSA9IHNlYXJjaF9ub2RlOwogICAgICAgICAgICAgICAgdWludDY0X3QgX2luZGV4OwogICAgICAgICAgICAgICAgLy8g0JzQsNC70LXQvdGM0LrQsNGPINCx0LDQu9Cw0L3RgdC40YDQvtCy0LrQsCwg0LXRgdC70Lgg0L/RgNCw0LLRi9C5INCy0LXRgSDQsdC+0LvRjNGI0LUg0LvQtdCy0L7Qs9C+INGC0L4g0YPQtNCw0LvRj9C10Lwg0YfQtdGA0LXQtyDQv9GA0LDQstC+CiAgICAgICAgICAgICAgICAvLyDQuNC90LDRh9C1INGH0LXRgNC10Lcg0LvQtdCy0L4KICAgICAgICAgICAgICAgIGlmIChzZWFyY2hfbm9kZS0+cmlnaHQtPndlaWdodCA+IHNlYXJjaF9ub2RlLT5sZWZ0LT53ZWlnaHQpIHsKICAgICAgICAgICAgICAgICAgICBfaW5kZXggPSBpbmRleF9ub2RlICsgMTsKICAgICAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICAgICAgX2luZGV4ID0gaW5kZXhfbm9kZSAtIDE7CiAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgLy8g0JjRidC10Lwg0YPQt9C10Lsg0YHQviDRgdC70LXQtNGD0Y7RidC40Lwg0LjQvdC00LXQutGB0L7QvC4KICAgICAgICAgICAgICAgIGZvciAoOzspIHsKICAgICAgICAgICAgICAgICAgICBpZiAoX2luZGV4ID09IGluZGV4X25vZGUpIHsKICAgICAgICAgICAgICAgICAgICAgICAgLy8g0KPQt9C10Lsg0L3QsNC50LTQtdC9CiAgICAgICAgICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAgICAgICAgIH0gZWxzZSBpZiAoX2luZGV4ID4gaW5kZXhfbm9kZSkgewogICAgICAgICAgICAgICAgICAgICAgICBzZWFyY2hfbm9kZS0+d2VpZ2h0LS07CiAgICAgICAgICAgICAgICAgICAgICAgIHNlYXJjaF9ub2RlID0gc2VhcmNoX25vZGUtPnJpZ2h0OwogICAgICAgICAgICAgICAgICAgICAgICBpbmRleF9ub2RlICs9ICh0aGlzLT5nZXRfY2hpbGRfd2VpZ2h0KHNlYXJjaF9ub2RlLT5sZWZ0KSArIDEpOwogICAgICAgICAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICAgICAgICAgIHNlYXJjaF9ub2RlLT53ZWlnaHQtLTsKCiAgICAgICAgICAgICAgICAgICAgICAgIHNlYXJjaF9ub2RlID0gc2VhcmNoX25vZGUtPmxlZnQ7CiAgICAgICAgICAgICAgICAgICAgICAgIGluZGV4X25vZGUgLT0gKHRoaXMtPmdldF9jaGlsZF93ZWlnaHQoc2VhcmNoX25vZGUtPnJpZ2h0KSArIDEpOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICBkZWxfbm9kZS0+ZGF0YSA9IHNlYXJjaF9ub2RlLT5kYXRhOwogICAgICAgICAgICAgICAgdGhpcy0+ZXJhc2Vfc2ltcGxlKHNlYXJjaF9ub2RlKTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgdGhpcy0+bm9kZV9mcmVlKHNlYXJjaF9ub2RlKTsKCiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9IGVsc2UgaWYgKGtleSA+IHNlYXJjaF9ub2RlLT5kYXRhLmtleSkgewogICAgICAgICAgICBzZWFyY2hfbm9kZS0+d2VpZ2h0LS07CiAgICAgICAgICAgIHNlYXJjaF9ub2RlID0gc2VhcmNoX25vZGUtPnJpZ2h0OwogICAgICAgICAgICBpbmRleF9ub2RlICs9ICh0aGlzLT5nZXRfY2hpbGRfd2VpZ2h0KHNlYXJjaF9ub2RlLT5sZWZ0KSArIDEpOwogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIHNlYXJjaF9ub2RlLT53ZWlnaHQtLTsKICAgICAgICAgICAgc2VhcmNoX25vZGUgPSBzZWFyY2hfbm9kZS0+bGVmdDsKICAgICAgICAgICAgaW5kZXhfbm9kZSAtPSAodGhpcy0+Z2V0X2NoaWxkX3dlaWdodChzZWFyY2hfbm9kZS0+cmlnaHQpICsgMSk7CiAgICAgICAgfQoKICAgIH0KfQoKdWludDY0X3QgYm50cmVlOjpnZXRfY2hpbGRfd2VpZ2h0KG5vZGVfdCAqbm9kZSkgewogICAgaWYgKG5vZGUpIHsKICAgICAgICByZXR1cm4gbm9kZS0+d2VpZ2h0OwogICAgfQoKICAgIHJldHVybiAwOwp9CgpkYXRhX3QgKmJudHJlZTo6Z2V0KHVpbnQ2NF90IGluZGV4KSB7CiAgICBpZiAoaW5kZXggPCAwIHx8IGluZGV4ID4gdGhpcy0+c2l6ZSgpIC0gMSkgewogICAgICAgIHJldHVybiBOVUxMOwogICAgfQoKICAgIG5vZGVfdCAqc2VhcmNoX25vZGUgPSB0aGlzLT50cmVlLT5yb290OwogICAgdWludDY0X3QgaW5kZXhfbm9kZSA9IHRoaXMtPmdldF9jaGlsZF93ZWlnaHQoc2VhcmNoX25vZGUtPmxlZnQpOwoKICAgIGZvciAoOzspIHsKICAgICAgICBpZiAoaW5kZXggPT0gaW5kZXhfbm9kZSkgewogICAgICAgICAgICByZXR1cm4gJnNlYXJjaF9ub2RlLT5kYXRhOwogICAgICAgIH0gZWxzZSBpZiAoaW5kZXggPiBpbmRleF9ub2RlKSB7CiAgICAgICAgICAgIHNlYXJjaF9ub2RlID0gc2VhcmNoX25vZGUtPnJpZ2h0OwogICAgICAgICAgICBpbmRleF9ub2RlICs9ICh0aGlzLT5nZXRfY2hpbGRfd2VpZ2h0KHNlYXJjaF9ub2RlLT5sZWZ0KSArIDEpOwogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIHNlYXJjaF9ub2RlID0gc2VhcmNoX25vZGUtPmxlZnQ7CiAgICAgICAgICAgIGluZGV4X25vZGUgLT0gKHRoaXMtPmdldF9jaGlsZF93ZWlnaHQoc2VhcmNoX25vZGUtPnJpZ2h0KSArIDEpOwogICAgICAgIH0KICAgIH0KfQoKZGF0YV90ICpibnRyZWU6OmdldChzdHJpbmcga2V5KSB7CiAgICBub2RlX3QgKnNlYXJjaF9ub2RlID0gdGhpcy0+dHJlZS0+cm9vdDsKICAgIHVpbnQ2NF90IGluZGV4X25vZGUgPSB0aGlzLT5nZXRfY2hpbGRfd2VpZ2h0KHNlYXJjaF9ub2RlLT5sZWZ0KTsKCiAgICBmb3IgKDs7KSB7CiAgICAgICAgaWYgKGtleSA9PSBzZWFyY2hfbm9kZS0+ZGF0YS5rZXkpIHsKICAgICAgICAgICAgcmV0dXJuICZzZWFyY2hfbm9kZS0+ZGF0YTsKICAgICAgICB9IGVsc2UgaWYgKGtleSA+IHNlYXJjaF9ub2RlLT5kYXRhLmtleSkgewogICAgICAgICAgICBzZWFyY2hfbm9kZSA9IHNlYXJjaF9ub2RlLT5yaWdodDsKICAgICAgICAgICAgaW5kZXhfbm9kZSArPSAodGhpcy0+Z2V0X2NoaWxkX3dlaWdodChzZWFyY2hfbm9kZS0+bGVmdCkgKyAxKTsKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICBzZWFyY2hfbm9kZSA9IHNlYXJjaF9ub2RlLT5sZWZ0OwogICAgICAgICAgICBpbmRleF9ub2RlIC09ICh0aGlzLT5nZXRfY2hpbGRfd2VpZ2h0KHNlYXJjaF9ub2RlLT5yaWdodCkgKyAxKTsKICAgICAgICB9CiAgICB9CgogICAgcmV0dXJuIE5VTEw7Cn0KCnVpbnQ2NF90IGJudHJlZTo6c2l6ZSgpIHsKICAgIGlmICh0aGlzLT50cmVlLT5yb290KSB7CiAgICAgICAgcmV0dXJuIHRoaXMtPnRyZWUtPnJvb3QtPndlaWdodDsKICAgIH0KCiAgICByZXR1cm4gMDsKfQoKdm9pZCBibnRyZWU6OnByaW50KCkgewogICAgdGhpcy0+cHJpbnQodGhpcy0+dHJlZS0+cm9vdCwgNSk7Cn0KCnZvaWQgYm50cmVlOjpwcmludChub2RlX3QgKnAsIGludCBpbmRlbnQpIHsKICAgIGlmIChwICE9IE5VTEwpIHsKICAgICAgICBpZiAocC0+cmlnaHQpIHsKICAgICAgICAgICAgdGhpcy0+cHJpbnQocC0+cmlnaHQsIGluZGVudCArIDQpOwogICAgICAgIH0KICAgICAgICBpZiAoaW5kZW50KSB7CiAgICAgICAgICAgIC8vc3RkOjpjb3V0IDw8IHN0ZDo6c2V0dyhpbmRlbnQpIDw8ICcgJyA8PCBwLT53ZWlnaHQgPDwgJyAnOwogICAgICAgICAgICBzdGQ6OmNvdXQgPDwgc3RkOjpzZXR3KGluZGVudCkgPDwgJyAnOwogICAgICAgIH0KICAgICAgICBpZiAocC0+cmlnaHQpIHsKICAgICAgICAgICAgc3RkOjpjb3V0IDw8ICIgL1xuIiA8PCBzdGQ6OnNldHcoaW5kZW50KSA8PCAnICc7CiAgICAgICAgfQogICAgICAgIC8vc3RkOjpjb3V0IDw8IHAtPmRhdGEua2V5IDw8ICI6IiA8PCBwLT5kYXRhLnZhbCA8PCAiXG4gIjsKICAgICAgICBzdGQ6OmNvdXQgPDwgcC0+ZGF0YS5rZXkgPDwgIjoiIDw8IHAgPDwgIjoiIDw8IHAtPnBhcmVudCA8PCAiXG4gIjsKICAgICAgICBpZiAocC0+bGVmdCkgewogICAgICAgICAgICBzdGQ6OmNvdXQgPDwgc3RkOjpzZXR3KGluZGVudCkgPDwgJyAnIDw8ICIgXFxcbiI7CiAgICAgICAgICAgIHRoaXMtPnByaW50KHAtPmxlZnQsIGluZGVudCArIDQpOwogICAgICAgIH0KICAgIH0KfQoKLyoKICog0JHQsNC70LDQvdGB0LjRgNC+0LLQutCwINC/0L7QstC+0YDQvtGC0L7QvAogKiDQkdCw0LvQsNC90YHQuNGA0L7QstC60LAg0LTQtdC70LDQtdGC0YHRjyDQvdCwINC+0YHQvdC+0LLQtSDQstC10YHQvtCyINC70LXQstC+0LPQviDQuCDQv9GA0LDQstC+0LPQviDQv9C+0LTQtNC10YDQtdCy0LAKICovCnZvaWQgYm50cmVlOjpiYWxhbmNlKG5vZGVfdCAqcCkgewogICAgaWYgKCFwKSB7CiAgICAgICAgcmV0dXJuOwogICAgfQoKICAgIG5vZGVfdCAqY2hpbGQgPSBOVUxMOwogICAgbm9kZV90ICpwYXJlbnQgPSBOVUxMOwogICAgdWludDY0X3QgbGQgPSAwOwogICAgdWludDY0X3QgcmQgPSAwOwoKICAgIGZvciAoOzspIHsKICAgICAgICBsZCA9IHRoaXMtPndlaWdodF90b19kZXB0aChwLT5sZWZ0KTsKICAgICAgICByZCA9IHRoaXMtPndlaWdodF90b19kZXB0aChwLT5yaWdodCk7CgogICAgICAgIGlmIChsZCA+IHJkICYmIGxkIC0gcmQgPiAxKSB7CiAgICAgICAgICAgIC8vINCf0YDQsNCy0YvQuSDQv9C+0LLQvtGA0L7Rgi4gCiAgICAgICAgICAgIC8vINCT0LvRg9Cx0LjQvdCwINC70LXQstC+0LPQviDQv9C+0LTQtNC10YDQtdCy0LAg0LHQvtC70YzRiNC1LCDRh9C10Lwg0LPQu9GD0LHQuNC90LAg0L/RgNCw0LLQvtCz0L4KCiAgICAgICAgICAgIGNoaWxkID0gcC0+bGVmdDsKICAgICAgICAgICAgcGFyZW50ID0gcC0+cGFyZW50OwoKICAgICAgICAgICAgaWYgKHBhcmVudCkgewogICAgICAgICAgICAgICAgaWYgKHBhcmVudC0+cmlnaHQgPT0gcCkgewogICAgICAgICAgICAgICAgICAgIHBhcmVudC0+cmlnaHQgPSBjaGlsZDsKICAgICAgICAgICAgICAgIH0gZWxzZSBpZiAocGFyZW50LT5sZWZ0ID09IHApIHsKICAgICAgICAgICAgICAgICAgICBwYXJlbnQtPmxlZnQgPSBjaGlsZDsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgIHRoaXMtPnRyZWUtPnJvb3QgPSBjaGlsZDsKICAgICAgICAgICAgfQogICAgICAgICAgICBjaGlsZC0+cGFyZW50ID0gcGFyZW50OwogICAgICAgICAgICBwLT5wYXJlbnQgPSBjaGlsZDsKCiAgICAgICAgICAgIHAtPmxlZnQgPSBjaGlsZC0+cmlnaHQ7CiAgICAgICAgICAgIGlmIChwLT5sZWZ0KSB7CiAgICAgICAgICAgICAgICBwLT5sZWZ0LT5wYXJlbnQgPSBwOwogICAgICAgICAgICB9CgogICAgICAgICAgICBjaGlsZC0+cmlnaHQgPSBwOwoKICAgICAgICAgICAgcC0+d2VpZ2h0ID0gMSArIHRoaXMtPmdldF9jaGlsZF93ZWlnaHQocC0+bGVmdCkgKyB0aGlzLT5nZXRfY2hpbGRfd2VpZ2h0KHAtPnJpZ2h0KTsKICAgICAgICAgICAgY2hpbGQtPndlaWdodCA9IDEgKyB0aGlzLT5nZXRfY2hpbGRfd2VpZ2h0KGNoaWxkLT5sZWZ0KSArIHRoaXMtPmdldF9jaGlsZF93ZWlnaHQoY2hpbGQtPnJpZ2h0KTsKICAgICAgICAgICAgCiAgICAgICAgICAgIC8vcCA9IGNoaWxkOwogICAgICAgICAgICBicmVhazsKICAgICAgICB9IGVsc2UgaWYgKHJkID4gbGQgJiYgcmQgLSBsZCA+IDEpIHsKICAgICAgICAgICAgLy8g0JvQtdCy0YvQuSDQv9C+0LLQvtGA0L7Rgi4gCiAgICAgICAgICAgIC8vINCT0LvRg9Cx0LjQvdCwINC/0YDQsNCy0L7Qs9C+INC/0L7QtNC00LXRgNC10LLQsCDQsdC+0LvRjNGI0LUsINGH0LXQvCDQs9C70YPQsdC40L3QsCDQu9C10LLQvtCz0L4KCiAgICAgICAgICAgIGNoaWxkID0gcC0+cmlnaHQ7CiAgICAgICAgICAgIHBhcmVudCA9IHAtPnBhcmVudDsKCiAgICAgICAgICAgIGlmIChwYXJlbnQpIHsKICAgICAgICAgICAgICAgIGlmIChwYXJlbnQtPnJpZ2h0ID09IHApIHsKICAgICAgICAgICAgICAgICAgICBwYXJlbnQtPnJpZ2h0ID0gY2hpbGQ7CiAgICAgICAgICAgICAgICB9IGVsc2UgaWYgKHBhcmVudC0+bGVmdCA9PSBwKSB7CiAgICAgICAgICAgICAgICAgICAgcGFyZW50LT5sZWZ0ID0gY2hpbGQ7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICB0aGlzLT50cmVlLT5yb290ID0gY2hpbGQ7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgY2hpbGQtPnBhcmVudCA9IHBhcmVudDsKICAgICAgICAgICAgcC0+cGFyZW50ID0gY2hpbGQ7CgogICAgICAgICAgICBwLT5yaWdodCA9IGNoaWxkLT5sZWZ0OwogICAgICAgICAgICBpZiAocC0+cmlnaHQpIHsKICAgICAgICAgICAgICAgIHAtPnJpZ2h0LT5wYXJlbnQgPSBwOwogICAgICAgICAgICB9CgogICAgICAgICAgICBjaGlsZC0+bGVmdCA9IHA7CgogICAgICAgICAgICBwLT53ZWlnaHQgPSAxICsgdGhpcy0+Z2V0X2NoaWxkX3dlaWdodChwLT5sZWZ0KSArIHRoaXMtPmdldF9jaGlsZF93ZWlnaHQocC0+cmlnaHQpOwogICAgICAgICAgICBjaGlsZC0+d2VpZ2h0ID0gMSArIHRoaXMtPmdldF9jaGlsZF93ZWlnaHQoY2hpbGQtPmxlZnQpICsgdGhpcy0+Z2V0X2NoaWxkX3dlaWdodChjaGlsZC0+cmlnaHQpOwoKICAgICAgICAgICAgLy9wID0gY2hpbGQ7CiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIH0KCiAgICAgICAgaWYgKHAtPnBhcmVudCkgewogICAgICAgICAgICBwID0gcC0+cGFyZW50OwogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIH0KICAgIH0KCiAgICByZXR1cm47Cn0KCi8qCiAqINCS0L7Qt9Cy0YDQsNGJ0LDQtdGCINC/0LXRgNCy0L7QtSDRh9C40YHQu9C+INCyINGB0YLQtdC/0LXQvdC4IDIsINC60L7RgtC+0YDQvtC1INCx0L7Qu9GM0YjQtSDQuNC70Lgg0YDQvtCy0L3QviB4CiAqLwp1aW50NjRfdCBibnRyZWU6OmNwbDIodWludDY0X3QgeCkgewogICAgeCA9IHggLSAxOwogICAgeCA9IHggfCAoeCA+PiAxKTsKICAgIHggPSB4IHwgKHggPj4gMik7CiAgICB4ID0geCB8ICh4ID4+IDQpOwogICAgeCA9IHggfCAoeCA+PiA4KTsKICAgIHggPSB4IHwgKHggPj4gMTYpOwogICAgeCA9IHggfCAoeCA+PiAzMik7CgogICAgcmV0dXJuIHggKyAxOwp9CgovKgogKiDQlNCy0L7QuNGH0L3Ri9C5INC70L7Qs9Cw0YDQuNGE0Lwg0L7RgiDRh9C40YHQu9CwCiAqLwpsb25nIGJudHJlZTo6aWxvZzIobG9uZyBkKSB7CiAgICBpbnQgcmVzdWx0OwogICAgc3RkOjpmcmV4cChkLCAmcmVzdWx0KTsKICAgIHJldHVybiByZXN1bHQgLSAxOwp9CgovKgogKiDQktC10YEg0Log0LPQu9GD0LHQuNC90LUKICovCnVpbnQ2NF90IGJudHJlZTo6d2VpZ2h0X3RvX2RlcHRoKG5vZGVfdCAqcCkgewogICAgaWYgKHAgPT0gTlVMTCkgewogICAgICAgIHJldHVybiAwOwogICAgfQoKICAgIGlmIChwLT53ZWlnaHQgPT0gMSkgewogICAgICAgIHJldHVybiAxOwogICAgfSBlbHNlIGlmIChwLT53ZWlnaHQgPT0gMikgewogICAgICAgIHJldHVybiAyOwogICAgfQoKICAgIHJldHVybiB0aGlzLT5pbG9nMih0aGlzLT5jcGwyKHAtPndlaWdodCkpOwp9CgppbnQgbWFpbih2b2lkKXsKICBibnRyZWUgdHJlZTsKICBpbnQgYXJyWzEzXSA9IHs4LCA0LCAzMCwgMiwgNiwgMTAsIDM2LCA5LCAxMiwzOCwgMTMsIDE0LCAxNSB9OwogIGZvcihpbnQgaT0wOyBpPDEzOyBpKyspIHsKICAgICBzdHJpbmcgemVyb19wYWRkZWQgPSBzdGQ6OnRvX3N0cmluZyhhcnJbaV0qMC4wMDAwMDEpLnN1YnN0cig0KTsgCiAgICAgdHJlZS5pbnNlcnQoemVyb19wYWRkZWQpOwogIH0KICB0cmVlLnByaW50KCk7Cn0=

Success #stdin #stdout 0s 4516KB

stdin

copy

Standard input is empty

stdout

copy

             0038:0x55bffa07d280:0x55bffa07d130
           /
         0036:0x55bffa07d130:0x55bffa07cf70
       /
     0030:0x55bffa07cf70:0
       \
                         0015:0x55bffa07d3d0:0x55bffa07d360
                       /
                     0014:0x55bffa07d360:0x55bffa07d2f0
                   /
                 0013:0x55bffa07d2f0:0x55bffa07d0c0
                   \
                     0012:0x55bffa07d210:0x55bffa07d2f0
               /
             0010:0x55bffa07d0c0:0x55bffa07ce90
               \
                 0009:0x55bffa07d1a0:0x55bffa07d0c0
           /
         0008:0x55bffa07ce90:0x55bffa07cf70
           \
                 0006:0x55bffa07d050:0x55bffa07cf00
               /
             0004:0x55bffa07cf00:0x55bffa07ce90
               \
                 0002:0x55bffa07cfe0:0x55bffa07cf00

https://ideone.com/recc7a

language:

C++14 (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language