代码

// 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 keeps the inherited
// nexthop when it lies in S(v), otherwise it emits the lowest-index nexthop of
// S(v).  Missing bit-branches get an explicit rule when the inherited nexthop
// differs from the local effective one.  Prefixes and the emitted table are
// sorted with LSD radix sorts.
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#include "routecomp.h"
#include <stdlib.h>
#include <string.h>

typedef unsigned long long u64;

static void radix_u64(u64 *a, int n, int nbytes) {
    if (n <= 1) return;
    u64 *tmp = (u64 *)malloc((size_t)n * 8);
    unsigned cnt[256];
    u64 *src = a, *dst = tmp;
    for (int shift = 0; shift < nbytes * 8; shift += 8) {
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; i++) cnt[(unsigned)(src[i] >> shift) & 255]++;
        unsigned acc = 0;
        for (int j = 0; j < 256; j++) { unsigned c = cnt[j]; cnt[j] = acc; acc += c; }
        for (int i = 0; i < n; i++) dst[cnt[(unsigned)(src[i] >> shift) & 255]++] = src[i];
        u64 *t = src; src = dst; dst = t;
    }
    if (src != a) memcpy(a, src, (size_t)n * 8);
    free(tmp);
}


static void radix_idx(const u64 *key, int *idx, int n, int nbytes) {
    if (n <= 1) return;
    int *tmp = (int *)malloc((size_t)n * 4);
    int *src = idx, *dst = tmp;
    unsigned cnt[256];
    for (int shift = 0; shift < nbytes * 8; shift += 8) {
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; i++) cnt[(unsigned)(key[src[i]] >> shift) & 255]++;
        unsigned acc = 0;
        for (int j = 0; j < 256; j++) { unsigned c = cnt[j]; cnt[j] = acc; acc += c; }
        for (int i = 0; i < n; i++) { int v = src[i]; dst[cnt[(unsigned)(key[v] >> shift) & 255]++] = v; }
        int *t = src; src = dst; dst = t;
    }
    if (src != idx) memcpy(idx, src, (size_t)n * 4);
    free(tmp);
}

static unsigned ht_k[256];
static int ht_v[256];
static inline int nh_idx(unsigned enc) {
    unsigned h = (enc * 2654435761u) >> 24;
    while (ht_k[h] != enc) h = (h + 1) & 255u;
    return ht_v[h];
}

static void emit1(RoutingTableEntry **out, int *outcnt, int *outcap, unsigned ip, unsigned len, unsigned nh) {
    if (*outcnt == *outcap) {
        *outcap *= 2;
        *out = (RoutingTableEntry *)realloc(*out, (size_t)(*outcap) * sizeof(RoutingTableEntry));
    }
    RoutingTableEntry *e = &(*out)[(*outcnt)++];
    e->addr = __builtin_bswap32(len ? (ip << (32 - len)) : 0u);
    e->len = (unsigned char)len;
    e->nexthop = nh;
    e->pad[0] = e->pad[1] = e->pad[2] = 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;
    // small radix sort of the 32-bit encodings
    {
        unsigned *tmp = (unsigned *)malloc((size_t)n * sizeof(unsigned));
        unsigned cnt[256];
        unsigned *src = ul, *dst = tmp;
        for (int shift = 0; shift < 32; shift += 8) {
            memset(cnt, 0, sizeof(cnt));
            for (int i = 0; i < n; i++) cnt[(src[i] >> shift) & 255]++;
            unsigned acc = 0;
            for (int j = 0; j < 256; j++) { unsigned c = cnt[j]; cnt[j] = acc; acc += c; }
            for (int i = 0; i < n; i++) dst[cnt[(src[i] >> shift) & 255]++] = src[i];
            unsigned *t = src; src = dst; dst = t;
        }
        if (src != ul) memcpy(ul, src, (size_t)n * sizeof(unsigned));
        free(tmp);
    }
    int nd = 1;
    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;
    memset(ht_k, 0, sizeof(ht_k));
    for (int i = 0; i < nd; i++) {
        unsigned v = ul[i];
        vals[i + 1] = v;
        unsigned h = (v * 2654435761u) >> 24;
        while (ht_k[h]) h = (h + 1) & 255u;
        ht_k[h] = v; ht_v[h] = i + 1;
    }

    // ---- pack prefixes and sort by (ip, len) ----
    u64 *key = (u64 *)malloc((size_t)n * 8);
    for (int i = 0; i < n; i++) {
        unsigned ip = __builtin_bswap32(tbl[i].addr);
        int idx = nh_idx(tbl[i].nexthop + 1u);
        key[i] = ((u64)ip << 14) | ((u64)tbl[i].len << 8) | (u64)idx;
    }
    radix_u64(key, n, 6);

    // ---- 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;
    int *path = (int *)malloc(34 * sizeof(int));
    path[0] = 0;
    int sp = 1;
    unsigned prev_k = 0;
    int prev_l = 0;
    for (int i = 0; i < n; i++) {
        u64 kv = key[i];
        unsigned ip = (unsigned)(kv >> 14);
        int len = (int)((kv >> 8) & 63);
        unsigned ni = (unsigned)(kv & 255);
        int lcp;
        if (i == 0) lcp = 0;
        else {
            unsigned x = ip ^ prev_k;
            lcp = x ? __builtin_clz(x) : 32;
            int m = len < prev_l ? len : prev_l;
            if (lcp > m) lcp = m;
        }
        while (sp - 1 > lcp) sp--;
        int v = path[lcp];
        for (int b = lcp; b < len; b++) {
            int bit = (int)((ip >> (31 - b)) & 1u);
            int c = cnt++;
            c0[c] = c1[c] = 0;
            eff[c] = eff[v];
            dep[c] = (unsigned char)(b + 1);
            ipv[c] = ip >> (32 - (b + 1));
            if (bit) c1[v] = c; else c0[v] = c;
            path[sp++] = c;
            v = c;
        }
        eff[v] = (unsigned char)ni;
        prev_k = ip; prev_l = len;
    }
    free(path);
    free(key);
    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) emit1(&out, &outcnt, &outcap, ipv[v], dep[v], vals[c] - 1u);
            nb = c;
        }
        if (bb) bg[bb] = nb;
        if (a) bg[a] = nb;
        unsigned ei = eff[v];
        if (a == 0 && bb != 0 && (int)ei != nb && ei != 0)
            emit1(&out, &outcnt, &outcap, ipv[v] << 1, dep[v] + 1u, vals[ei] - 1u);
        if (bb == 0 && a != 0 && (int)ei != nb && ei != 0)
            emit1(&out, &outcnt, &outcap, (ipv[v] << 1) | 1u, dep[v] + 1u, vals[ei] - 1u);
    }
    free(bg); free(S); free(ipv); free(dep); free(eff); free(c1); free(c0);

    // ---- sort output by (addr, len) ----
    {
        u64 *ok = (u64 *)malloc((size_t)outcnt * 8);
        int *idx = (int *)malloc((size_t)outcnt * 4);
        for (int j = 0; j < outcnt; j++) {
            ok[j] = ((u64)out[j].addr << 8) | (u64)out[j].len;
            idx[j] = j;
        }
        radix_idx(ok, idx, outcnt, 5);
        RoutingTableEntry *o2 = (RoutingTableEntry *)malloc((size_t)outcnt * sizeof(RoutingTableEntry));
        for (int j = 0; j < outcnt; j++) o2[j] = out[idx[j]];
        free(ok); free(idx); free(out);
        out = o2;
    }

    *tbl_comp = out;
    *n_comp = outcnt;
}

评测结果