代码

// This code is AI-generated. (AI 生成的代码)
// routecomp: optimal routing-table compression (ORTC).
//
// Build a binary trie over the prefixes.  Each node stores the effective
// nexthop inherited from its nearest explicit ancestor.  Bottom-up compute the
// set S(v) of nexthops that must survive in v's subtree: a leaf needs its own
// effective nexthop; an internal node needs the intersection of its children's
// sets if non-empty, otherwise their union (a branch with no child behaves like
// a leaf carrying the effective nexthop).  Top-down, a node inherits the
// parent's chosen nexthop if that nexthop is in S(v); otherwise it emits a rule
// for the smallest-index nexthop in S(v).  Missing bit-branches get an explicit
// rule when the inherited nexthop differs from the local effective one.  The
// emitted table is then sorted by (addr, len).
#include "routecomp.h"
#include <stdlib.h>
#include <string.h>

typedef unsigned long long u64;

struct Pref { unsigned ip; unsigned len; unsigned nh; };

static int cmp_u32(const void *a, const void *b) {
    unsigned x = *(const unsigned *)a, y = *(const unsigned *)b;
    return x < y ? -1 : (x > y ? 1 : 0);
}
static int cmp_pref(const void *a, const void *b) {
    const struct Pref *x = (const struct Pref *)a, *y = (const struct Pref *)b;
    if (x->ip != y->ip) return x->ip < y->ip ? -1 : 1;
    return x->len < y->len ? -1 : (x->len > y->len ? 1 : 0);
}
static int cmp_entry(const void *a, const void *b) {
    const RoutingTableEntry *x = (const RoutingTableEntry *)a, *y = (const RoutingTableEntry *)b;
    if (x->addr != y->addr) return x->addr < y->addr ? -1 : 1;
    return x->len < y->len ? -1 : (x->len > y->len ? 1 : 0);
}

void compress(const RoutingTableEntry *tbl, int n, RoutingTableEntry **tbl_comp, int *n_comp) {
    // ---- distinct nexthops -> encodings raw+1, sorted ----
    unsigned *ul = (unsigned *)malloc((size_t)n * sizeof(unsigned));
    for (int i = 0; i < n; i++) ul[i] = tbl[i].nexthop + 1u;
    qsort(ul, n, sizeof(unsigned), cmp_u32);
    int nd = 1;                                  // number of distinct enc values
    for (int i = 1; i < n; i++)
        if (ul[i] != ul[nd - 1]) ul[nd++] = ul[i];
    int D = nd + 1;                              // vals[0] = 0 (none)
    unsigned *vals = (unsigned *)malloc((size_t)D * sizeof(unsigned));
    vals[0] = 0;
    for (int i = 0; i < nd; i++) vals[i + 1] = ul[i];

    // ---- prefixes, sorted by (ip, len) ----
    struct Pref *P = (struct Pref *)malloc((size_t)n * sizeof(struct Pref));
    for (int i = 0; i < n; i++) {
        P[i].ip = __builtin_bswap32(tbl[i].addr);
        P[i].len = tbl[i].len;
        unsigned enc = tbl[i].nexthop + 1u;
        int lo = 1, hi = D - 1;
        while (lo <= hi) {
            int mid = (lo + hi) >> 1;
            if (vals[mid] < enc) lo = mid + 1;
            else if (vals[mid] > enc) hi = mid - 1;
            else { P[i].nh = (unsigned)mid; break; }
        }
    }
    qsort(P, n, sizeof(struct Pref), cmp_pref);

    // ---- trie ----
    size_t maxn = (size_t)n * 33 + 2;
    int *c0 = (int *)malloc(maxn * sizeof(int));
    int *c1 = (int *)malloc(maxn * sizeof(int));
    unsigned char *eff = (unsigned char *)malloc(maxn);
    unsigned char *dep = (unsigned char *)malloc(maxn);
    unsigned *ipv = (unsigned *)malloc(maxn * sizeof(unsigned));
    c0[0] = c1[0] = 0; eff[0] = 0; dep[0] = 0; ipv[0] = 0;
    int cnt = 1;
    for (int i = 0; i < n; i++) {
        unsigned ip = P[i].ip, len = P[i].len, ni = P[i].nh;
        int v = 0;
        unsigned cur = 0;
        for (unsigned b = 0; b < len; b++) {
            unsigned bit = (ip >> (31 - b)) & 1u;
            cur = (cur << 1) | bit;
            int c = bit ? c1[v] : c0[v];
            if (!c) {
                c = cnt++;
                c0[c] = c1[c] = 0; eff[c] = eff[v]; dep[c] = (unsigned char)(b + 1); ipv[c] = cur;
                if (bit) c1[v] = c; else c0[v] = c;
            }
            v = c;
        }
        eff[v] = (unsigned char)ni;
    }
    free(P);
    free(ul);
    int N = cnt;

    // ---- bottom-up sets ----
    u64 *S = (u64 *)malloc((size_t)N * sizeof(u64));
    for (int v = N - 1; v >= 0; v--) {
        int a = c0[v], b = c1[v];
        unsigned ei = eff[v];
        if (a == 0 && b == 0) {
            S[v] = 1ULL << ei;
        } else {
            u64 s0 = a ? S[a] : (1ULL << ei);
            u64 s1 = b ? S[b] : (1ULL << ei);
            u64 in = s0 & s1;
            S[v] = in ? in : (s0 | s1);
        }
    }

    // ---- top-down emit ----
    int outcap = n + 16, outcnt = 0;
    RoutingTableEntry *out = (RoutingTableEntry *)malloc((size_t)outcap * sizeof(RoutingTableEntry));
    int *bg = (int *)malloc((size_t)N * sizeof(int));
    bg[0] = 0;
    for (int v = 0; v < N; v++) {
        int b = bg[v];
        int a = c0[v], bb = c1[v];
        u64 sv = S[v];
        int nb;
        if ((sv >> b) & 1ULL) {
            nb = b;
        } else {
            int c = __builtin_ctzll(sv);
            if (c != 0) {
                if (outcnt == outcap) { outcap *= 2; out = (RoutingTableEntry *)realloc(out, (size_t)outcap * sizeof(RoutingTableEntry)); }
                RoutingTableEntry *e = &out[outcnt++];
                unsigned len = dep[v];
                e->addr = __builtin_bswap32(len ? (ipv[v] << (32 - len)) : 0u);
                e->len = (unsigned char)len;
                e->nexthop = vals[c] - 1u;
                e->pad[0] = e->pad[1] = e->pad[2] = 0;
            }
            nb = c;
        }
        if (bb) bg[bb] = nb;
        if (a) bg[a] = nb;
        unsigned ei = eff[v];
        if (a == 0 && bb != 0 && (int)ei != nb) {
            if (outcnt == outcap) { outcap *= 2; out = (RoutingTableEntry *)realloc(out, (size_t)outcap * sizeof(RoutingTableEntry)); }
            RoutingTableEntry *e = &out[outcnt++];
            unsigned len = dep[v] + 1u;
            e->addr = __builtin_bswap32((ipv[v] << 1) << (32 - len));
            e->len = (unsigned char)len;
            e->nexthop = vals[ei] - 1u;
            e->pad[0] = e->pad[1] = e->pad[2] = 0;
        }
        if (bb == 0 && a != 0 && (int)ei != nb) {
            if (outcnt == outcap) { outcap *= 2; out = (RoutingTableEntry *)realloc(out, (size_t)outcap * sizeof(RoutingTableEntry)); }
            RoutingTableEntry *e = &out[outcnt++];
            unsigned len = dep[v] + 1u;
            e->addr = __builtin_bswap32(((ipv[v] << 1) | 1u) << (32 - len));
            e->len = (unsigned char)len;
            e->nexthop = vals[ei] - 1u;
            e->pad[0] = e->pad[1] = e->pad[2] = 0;
        }
    }
    free(bg); free(S); free(ipv); free(dep); free(eff); free(c1); free(c0);

    qsort(out, outcnt, sizeof(RoutingTableEntry), cmp_entry);
    *tbl_comp = out;
    *n_comp = outcnt;
}

评测结果