代码

#include "routecomp.h"

#include <algorithm>
#include <cstdint>
#include <cstdlib>
#include <vector>

namespace {

enum : unsigned char {
    OP_LEAF = 0,
    OP_INTERSECTION = 1,
    OP_UNION = 2,
};

enum : unsigned char {
    EDGE_MISSING = 0,
    EDGE_DIRECT = 1,
    EDGE_ONE_SINGLETON = 2,
    EDGE_ONE_UNION = 3,
    EDGE_MANY_SINGLETON = 4,
};

struct Node {
    uint32_t prefix;
    uint32_t label;
    uint32_t target;
    uint32_t representative;
    int child[2];
    uint32_t base_cost;
    unsigned char length;
    unsigned char has_label;
    unsigned char operation;
    unsigned char edge_mode[2];

    Node(uint32_t p, unsigned len)
        : prefix(p), label(0), target(0), representative(0),
          child{-1, -1}, base_cost(0), length((unsigned char)len),
          has_label(0), operation(OP_LEAF),
          edge_mode{EDGE_MISSING, EDGE_MISSING} {}
};

struct SetResult {
    std::vector<uint32_t> values;
    uint32_t cost;
};

static std::vector<Node> nodes;
static RoutingTableEntry *answer;
static int answer_count;

static inline uint32_t prefix_mask(unsigned length) {
    return length ? 0xffffffffu << (32 - length) : 0u;
}

static inline unsigned common_length(uint32_t a, uint32_t b,
                                     unsigned limit) {
    uint32_t difference = a ^ b;
    unsigned common = difference ? (unsigned)__builtin_clz(difference) : 32u;
    return common < limit ? common : limit;
}

static int make_node(uint32_t prefix, unsigned length) {
    nodes.emplace_back(prefix & prefix_mask(length), length);
    return (int)nodes.size() - 1;
}

static void insert_prefix(uint32_t prefix, unsigned length, uint32_t value) {
    prefix &= prefix_mask(length);
    int current = 0;
    if (length == 0) {
        nodes[0].label = value;
        nodes[0].has_label = 1;
        return;
    }

    for (;;) {
        Node &parent = nodes[current];
        unsigned direction = (prefix >> (31 - parent.length)) & 1u;
        int next = parent.child[direction];
        if (next < 0) {
            int created = make_node(prefix, length);
            nodes[created].label = value;
            nodes[created].has_label = 1;
            nodes[current].child[direction] = created;
            return;
        }

        unsigned limit = std::min<unsigned>(length, nodes[next].length);
        unsigned common = common_length(prefix, nodes[next].prefix, limit);
        if (common == nodes[next].length) {
            if (common == length) {
                nodes[next].label = value;
                nodes[next].has_label = 1;
                return;
            }
            current = next;
            continue;
        }

        int branch = make_node(prefix, common);
        nodes[current].child[direction] = branch;
        unsigned old_direction =
            (nodes[next].prefix >> (31 - common)) & 1u;
        nodes[branch].child[old_direction] = next;
        if (common == length) {
            nodes[branch].label = value;
            nodes[branch].has_label = 1;
        } else {
            int created = make_node(prefix, length);
            nodes[created].label = value;
            nodes[created].has_label = 1;
            unsigned new_direction = (prefix >> (31 - common)) & 1u;
            nodes[branch].child[new_direction] = created;
        }
        return;
    }
}

static SetResult solve_node(int index, uint32_t inherited_target) {
    Node &node = nodes[index];
    uint32_t current_target = node.has_label ? node.label : inherited_target;
    node.target = current_target;

    if (node.length == 32) {
        node.operation = OP_LEAF;
        node.base_cost = 0;
        node.representative = current_target;
        return SetResult{{current_target}, 0};
    }

    SetResult side[2];
    for (unsigned direction = 0; direction < 2; ++direction) {
        int child = node.child[direction];
        if (child < 0) {
            side[direction].values.push_back(current_target);
            side[direction].cost = 0;
            node.edge_mode[direction] = EDGE_MISSING;
            continue;
        }

        side[direction] = solve_node(child, current_target);
        unsigned virtual_levels =
            nodes[child].length - (unsigned)node.length - 1u;
        if (virtual_levels == 0) {
            node.edge_mode[direction] = EDGE_DIRECT;
            continue;
        }

        std::vector<uint32_t> &set = side[direction].values;
        std::vector<uint32_t>::iterator position =
            std::lower_bound(set.begin(), set.end(), current_target);
        bool contains = position != set.end() && *position == current_target;
        if (!contains) ++side[direction].cost;

        if (virtual_levels >= 2) {
            set.assign(1, current_target);
            node.edge_mode[direction] = EDGE_MANY_SINGLETON;
        } else if (contains) {
            set.assign(1, current_target);
            node.edge_mode[direction] = EDGE_ONE_SINGLETON;
        } else {
            set.insert(position, current_target);
            node.edge_mode[direction] = EDGE_ONE_UNION;
        }
    }

    std::vector<uint32_t> intersection;
    intersection.reserve(std::min(side[0].values.size(),
                                  side[1].values.size()));
    std::set_intersection(side[0].values.begin(), side[0].values.end(),
                          side[1].values.begin(), side[1].values.end(),
                          std::back_inserter(intersection));

    SetResult result;
    if (!intersection.empty()) {
        result.values.swap(intersection);
        result.cost = side[0].cost + side[1].cost;
        node.operation = OP_INTERSECTION;
    } else {
        result.values.reserve(side[0].values.size() + side[1].values.size());
        std::set_union(side[0].values.begin(), side[0].values.end(),
                       side[1].values.begin(), side[1].values.end(),
                       std::back_inserter(result.values));
        result.cost = side[0].cost + side[1].cost + 1;
        node.operation = OP_UNION;
    }
    node.base_cost = result.cost;
    node.representative = result.values.front();
    return result;
}

static bool set_contains(int index, uint32_t value);

static inline bool edge_contains(const Node &node, unsigned direction,
                                 uint32_t value) {
    int child = node.child[direction];
    switch (node.edge_mode[direction]) {
        case EDGE_MISSING:
        case EDGE_ONE_SINGLETON:
        case EDGE_MANY_SINGLETON:
            return value == node.target;
        case EDGE_DIRECT:
            return set_contains(child, value);
        default:
            return value == node.target || set_contains(child, value);
    }
}

static bool set_contains(int index, uint32_t value) {
    const Node &node = nodes[index];
    if (node.length == 32 || node.operation == OP_LEAF)
        return value == node.target;
    bool left = edge_contains(node, 0, value);
    if (node.operation == OP_UNION)
        return left || edge_contains(node, 1, value);
    return left && edge_contains(node, 1, value);
}

static inline void emit(uint32_t prefix, unsigned length, uint32_t value) {
    RoutingTableEntry &entry = answer[answer_count++];
    entry.addr = __builtin_bswap32(prefix & prefix_mask(length));
    entry.len = (unsigned char)length;
    entry.pad[0] = entry.pad[1] = entry.pad[2] = 0;
    entry.nexthop = value;
}

static void reconstruct(int index, uint32_t inherited_output) {
    const Node &node = nodes[index];
    uint32_t selected = inherited_output;
    if (!set_contains(index, selected)) {
        selected = node.representative;
        emit(node.prefix, node.length, selected);
    }
    if (node.length == 32) return;

    for (unsigned direction = 0; direction < 2; ++direction) {
        int child = node.child[direction];
        unsigned mode = node.edge_mode[direction];
        uint32_t immediate_prefix = node.prefix |
            (direction << (31 - node.length));

        if (mode == EDGE_MISSING) {
            if (selected != node.target)
                emit(immediate_prefix, node.length + 1, node.target);
            continue;
        }
        if (mode == EDGE_DIRECT) {
            reconstruct(child, selected);
            continue;
        }
        if (mode == EDGE_ONE_SINGLETON || mode == EDGE_MANY_SINGLETON) {
            if (selected != node.target)
                emit(immediate_prefix, node.length + 1, node.target);
            reconstruct(child, node.target);
            continue;
        }

        uint32_t virtual_selected = selected;
        if (virtual_selected != node.target &&
            !set_contains(child, virtual_selected)) {
            virtual_selected = node.target;
            emit(immediate_prefix, node.length + 1, virtual_selected);
        }

        unsigned continuation_direction =
            (nodes[child].prefix >> (30 - node.length)) & 1u;
        if (virtual_selected != node.target) {
            uint32_t missing_prefix = immediate_prefix |
                ((continuation_direction ^ 1u) << (30 - node.length));
            emit(missing_prefix, node.length + 2, node.target);
        }
        reconstruct(child, virtual_selected);
    }
}

}  // namespace

void compress(const RoutingTableEntry *tbl, int n,
              RoutingTableEntry **tbl_comp, int *n_comp) {
    nodes.clear();
    nodes.reserve((size_t)n * 2u + 1u);
    make_node(0, 0);

    for (int i = 0; i < n; ++i) {
        unsigned length = tbl[i].len;
        uint32_t prefix = __builtin_bswap32(tbl[i].addr);
        insert_prefix(prefix, length, tbl[i].nexthop);
    }

    SetResult root = solve_node(0, 0);
    size_t capacity = (size_t)n * 2u + 2u;
    answer = (RoutingTableEntry *)std::malloc(
        capacity * sizeof(RoutingTableEntry));
    answer_count = 0;
    reconstruct(0, 0);

    *tbl_comp = answer;
    *n_comp = answer_count;
}

评测结果