#include <iostream>

using namespace std;

template<class K, class V, class H = hash<K>, int SIZE = 1024>
class LRUCache {
private:
    struct Node {
        K key;
        V value;
        Node *hash_prev;
        Node *hash_next;
        Node *list_prev;
        Node *list_next;

        Node() = default;
    };

public:
    LRUCache() : count(0), hash_map(), head(nullptr), tail(nullptr) {}

    ~LRUCache() {
        for (Node *p = head, *n = nullptr; p; n = p->list_next, delete (p), p = n);
    }

private:
    Node *find(const K &key) {
        size_t hash_key = hash(key) % SIZE;
        for (Node *p = hash_map[hash_key].hash_next; p; p = p->hash_next) {
            if (p->key == key) {
                return p;
            }
        }
        return nullptr;
    }

public:
    bool get(const K &key, V &value) {
        Node *target = find(key);
        if (target) {
            value = target->value;
            return true;
        }

        return false;
    }

    void put(const K &key, const V &value) {
        Node *target = find(key);

        if (target) {
            target->value = value;
            if (target->list_prev)target->list_prev->list_next = target->list_next;
            if (target->list_next)target->list_next->list_prev = target->list_prev;
            target->list_prev = nullptr;
            target->list_next = head;
            head->list_prev = target;
            head = target;
            return;
        }

        target = new Node();
        target->key = key;
        target->value = value;
        target->list_next = head;
        if (head)head->list_prev = target;
        head = target;
        if (tail == nullptr)tail = target;

        size_t hash_key = hash(key) % SIZE;
        if (hash_map[hash_key].hash_prev == nullptr) {
            hash_map[hash_key].hash_prev = target;
            hash_map[hash_key].hash_next = target;
        } else {
            target->hash_prev = hash_map[hash_key].hash_prev;
            hash_map[hash_key].hash_prev->hash_next = target;
            hash_map[hash_key].hash_prev = target;
        }

        if (count<SIZE) {
            count++;
            return;
        }

        Node *new_tail = tail;
        if (tail->hash_prev)tail->hash_prev->hash_next = tail->hash_next;
        if (tail->hash_next)tail->hash_next->hash_prev = tail->hash_prev;
        delete (tail);

        tail = new_tail;
        tail->list_next = nullptr;
    }

private:
    size_t count;
    Node hash_map[SIZE];
    Node *head;
    Node *tail;
    H hash;
};

#include <iostream>

using namespace std;

template<class T>
void quick_sort(T *data, size_t n) {
    if (n <= 1)return;

    size_t k = 1;
    for (size_t i = 1; i < n; i++) {
        if (data[i] < data[k - 1]) {
            swap(data[k - 1], data[i]);
            k++;
        }
    }

    quick_sort(data, k);
    quick_sort(data + k, n - k);
}

#include <iostream>
#include <vector>

struct Node {
  int value;
  Node *left;
  Node *right;

  Node(const int &value, Node *left = nullptr, Node *right = nullptr) : value(value), left(left), right(right) {}
};

Node *find_path(Node *node, Node *n1, Node *n2, std::vector<Node *> &path) {
  path.push_back(node);
  if (node == n1 || node == n2)return node;

  Node *result = nullptr;
  if (node->left && (result = find_path(node->left, n1, n2, path))) return result;
  if (node->right && (result = find_path(node->right, n1, n2, path))) return result;

  path.pop_back();
  return nullptr;
}

bool find_child(Node *node, Node *child) {
  return node == child || (node->left && find_child(node->left, child)) ||
         (node->right && find_child(node->right, child));
}

Node *find_parent(Node *node, Node *n1, Node *n2) {
  std::vector<Node *> path;
  auto n = find_path(node, n1, n2, path);
  if (!n)return n;

  Node *last = nullptr, *target = n == n1 ? n2 : n1;
  for (auto iter = path.rbegin(); iter != path.rend(); iter++) {
    Node *parent = *iter;
    if (last) {
      parent = last == parent->left ? parent->right : parent->left;
    }
    if (find_child(parent, target))return *iter;
    last = *iter;
  }

  return nullptr;
}

#ifndef PYTHON_EXAMPLE_H
#define PYTHON_EXAMPLE_H

int fact(int n);

#endif //PYTHON_EXAMPLE_H

#include "example.h"

int fact(int n) {
    if (n < 0) return 0;
    else if (n == 0) return 1;
    else return n * fact(n - 1);
}

#include <llvm/IR/Module.h>
#include <llvm/IR/IRBuilder.h>
#include <llvm/IR/LLVMContext.h>
#include <llvm/Support/TargetSelect.h>
#include <llvm/Bitcode/BitcodeWriter.h>
#include <llvm/Support/raw_os_ostream.h>
#include <llvm/ExecutionEngine/ExecutionEngine.h>
#include <llvm/ExecutionEngine/GenericValue.h>

#include <string>
#include <vector>
#include <iostream>
#include <fstream>

using namespace std;
using namespace llvm;

int main() {
    LLVMContext context;
    IRBuilder<> builder(context);
    Module module("test", context);

    /*1.声明puts函数*/
    FunctionType *puts_type = FunctionType::get(builder.getInt32Ty(), {builder.getInt8PtrTy()}, true);
    Constant *puts_func = module.getOrInsertFunction("puts", puts_type);  // puts? printf?

    /*2.定义main函数*/
    FunctionType *main_type = FunctionType::get(builder.getInt32Ty(), false);
    Function *main_func = Function::Create(main_type, Function::ExternalLinkage, "main", &module);

    BasicBlock *main_body = BasicBlock::Create(context, "entry", main_func);
    builder.SetInsertPoint(main_body);

    CallInst *ret_value = builder.CreateCall(puts_func, builder.CreateGlobalStringPtr("Hello,world!!!"));
    builder.CreateRet(ret_value);

    /*3.output*/
    fstream fs("test.bc");  // lli test.bc
    raw_os_ostream out(fs);
    WriteBitcodeToFile(module, out);
    outs() << module;

    /*4.JIT*/
    InitializeNativeTarget();
    InitializeNativeTargetAsmPrinter();

    unique_ptr<Module> owner(&module);
    ExecutionEngine *engine = EngineBuilder(move(owner)).create();

    GenericValue gv = engine->runFunction(main_func, {});
    outs() << "Result: " << gv.IntVal;  // 获取函数调用结果

    return 0;
}