代码

#include "routecomp.h"
#include <stdlib.h>
#include <string.h>

typedef struct { int c0, c1; unsigned nh; } Node;
static Node *tr;
static int cnt;
static RoutingTableEntry *out;

static unsigned *ipv;
static unsigned char *lenv;
static int *parent;

// distinct encoded values -> indices
static unsigned *vals;   // vals[0] = 0 (none), vals[1..D-1] = sorted distinct tr[].nh
static int D;

static unsigned long long *S;   // bitmask per node
static int *best;

static int outcnt, outcap;
static void emitOne(unsigned ip, unsigned char len, unsigned nh) {
    if (outcnt >= outcap) { outcap = outcap * 2; out = (RoutingTableEntry*)realloc(out, (size_t)outcap * sizeof(RoutingTableEntry)); }
    RoutingTableEntry e;
    e.addr = __builtin_bswap32(ip << (32 - len));
    e.len = len;
    e.nexthop = nh;
    e.pad[0] = e.pad[1] = e.pad[2] = 0;
    out[outcnt++] = e;
}

static int cmpEntry(const void *x, const void *y) {
    const RoutingTableEntry *a = (const RoutingTableEntry*)x;
    const RoutingTableEntry *b = (const RoutingTableEntry*)y;
    if (a->addr != b->addr) return a->addr < b->addr ? -1 : 1;
    return (int)a->len - (int)b->len;
}

static int cmpUnsigned(const void *x, const void *y) {
    unsigned a = *(const unsigned*)x, b = *(const unsigned*)y;
    return a < b ? -1 : (a > b ? 1 : 0);
}

void compress(const RoutingTableEntry *tbl, int n, RoutingTableEntry **tbl_comp, int *n_comp) {
    size_t maxn = (size_t)n * 33 + 2;
    tr = (Node*)malloc(maxn * sizeof(Node));
    cnt = 0;
    tr[0].c0 = tr[0].c1 = 0; tr[0].nh = 0; cnt = 1;
    for (int i = 0; i < n; i++) {
        unsigned ip = __builtin_bswap32(tbl[i].addr);
        int len = tbl[i].len;
        unsigned h = tbl[i].nexthop;
        int node = 0;
        for (int b = 0; b < len; b++) {
            int bit = (ip >> (31 - b)) & 1;
            int *c = bit ? &tr[node].c1 : &tr[node].c0;
            if (*c == 0) { tr[cnt].c0 = tr[cnt].c1 = 0; tr[cnt].nh = 0; *c = cnt++; }
            node = *c;
        }
        tr[node].nh = h + 1;
    }
    int N = cnt;
    parent = (int*)malloc((size_t)N * sizeof(int));
    ipv = (unsigned*)malloc((size_t)N * sizeof(unsigned));
    lenv = (unsigned char*)malloc((size_t)N);
    int *stack = (int*)malloc((size_t)(N + 2) * sizeof(int));
    int *ord = (int*)malloc((size_t)N * sizeof(int));
    int sp = 0, oi = 0;
    stack[sp++] = 0; parent[0] = -1; ipv[0] = 0; lenv[0] = 0;
    while (sp > 0) {
        int v = stack[--sp];
        ord[oi++] = v;
        int c0 = tr[v].c0, c1 = tr[v].c1;
        if (c1) { parent[c1] = v; ipv[c1] = (ipv[v] << 1) | 1u; lenv[c1] = lenv[v] + 1; stack[sp++] = c1; }
        if (c0) { parent[c0] = v; ipv[c0] = (ipv[v] << 1); lenv[c0] = lenv[v] + 1; stack[sp++] = c0; }
    }
    // collect distinct encoded nh values (non-zero), plus 0 (none)
    vals = (unsigned*)malloc((size_t)(N + 2) * sizeof(unsigned));
    int nv = 0;
    for (int v = 0; v < N; v++) if (tr[v].nh != 0) vals[nv++] = tr[v].nh;
    qsort(vals, nv, sizeof(unsigned), cmpUnsigned);
    int m = 0;
    for (int i = 0; i < nv; i++) if (m == 0 || vals[i] != vals[m - 1]) vals[m++] = vals[i];
    D = m + 1; // index 0 = "none" (value 0)
    // shift vals right by one, put 0 at index 0
    for (int i = m; i >= 1; i--) vals[i] = vals[i - 1];
    vals[0] = 0;
    // map helper: idx of encoded value (binary search)
    // compute idx_eff[v] on the fly in bottom-up? we need idx_eff for leaves.
    int *idx_eff = (int*)malloc((size_t)N * sizeof(int));
    for (int i = 0; i < N; i++) {
        int v = ord[i];
        if (tr[v].nh != 0) {
            // binary search tr[v].nh in vals[1..D-1]
            unsigned x = tr[v].nh;
            int lo = 1, hi = D - 1;
            while (lo <= hi) { int mid = (lo + hi) >> 1; if (vals[mid] < x) lo = mid + 1; else if (vals[mid] > x) hi = mid - 1; else { lo = mid; break; } }
            idx_eff[v] = lo;
        } else {
            idx_eff[v] = (v == 0) ? 0 : idx_eff[parent[v]];
        }
    }
    S = (unsigned long long*)malloc((size_t)N * sizeof(unsigned long long));
    best = (int*)malloc((size_t)N * sizeof(int));
    for (int i = N - 1; i >= 0; i--) {
        int v = ord[i];
        int c0 = tr[v].c0, c1 = tr[v].c1;
        if (c0 == 0 && c1 == 0) {
            S[v] = 1ULL << idx_eff[v];
            best[v] = 0;
        } else if (c0 == 0 || c1 == 0) {
            // one empty child: background forced to eff[v]
            int child = c0 ? c0 : c1;
            int idx = idx_eff[v];
            if ((S[child] >> idx) & 1ULL) best[v] = best[child];
            else best[v] = 1 + best[child];
            S[v] = 1ULL << idx;
        } else {
            int base = best[c0] + best[c1];
            unsigned long long s0 = S[c0], s1 = S[c1];
            unsigned long long inter = s0 & s1;
            if (inter) { S[v] = inter; best[v] = base; }
            else { S[v] = s0 | s1; best[v] = base + 1; }
        }
    }
    outcap = n + 16;
    out = (RoutingTableEntry*)malloc((size_t)outcap * sizeof(RoutingTableEntry));
    outcnt = 0;
    // top-down emission
    // background per node (index). process in preorder (ord) carrying bg via stack.
    int *bg = (int*)malloc((size_t)N * sizeof(int));
    bg[0] = 0; // none
    for (int i = 0; i < N; i++) {
        int v = ord[i];
        int b = bg[v];
        int c0 = tr[v].c0, c1 = tr[v].c1;
        int nb;
        if ((S[v] >> b) & 1ULL) {
            nb = b;
        } else {
            unsigned long long sv = S[v];
            int c = __builtin_ctzll(sv); // lowest set bit index
            if (c != 0) {
                emitOne(ipv[v], lenv[v], vals[c] - 1);
            }
            nb = c;
        }
        if (c1) bg[c1] = nb;
        if (c0) bg[c0] = nb;
    }
    free(parent); free(ipv); free(lenv); free(stack); free(ord); free(idx_eff); free(S); free(best); free(vals); free(tr);
    qsort(out, outcnt, sizeof(RoutingTableEntry), cmpEntry);
    *tbl_comp = out;
    *n_comp = outcnt;
}

评测结果