代码

#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 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;
}

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;
    int *parent = (int*)malloc((size_t)N * sizeof(int));
    unsigned *eff = (unsigned*)malloc((size_t)N * sizeof(unsigned));
    unsigned *ipv = (unsigned*)malloc((size_t)N * sizeof(unsigned));
    unsigned char *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; }
    }
    // dead-entry detection (bottom-up): below[], coveredBelow[], dead[]
    unsigned char *below = (unsigned char*)malloc((size_t)N);
    unsigned char *coveredBelow = (unsigned char*)malloc((size_t)N);
    unsigned char *dead = (unsigned char*)malloc((size_t)N);
    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) below[v] = 0;
        else below[v] = coveredBelow[c0] && coveredBelow[c1];
        coveredBelow[v] = (tr[v].nh != 0) || below[v];
        dead[v] = (tr[v].nh != 0) && below[v];
    }
    // effective nexthop (top-down), skipping dead entries
    for (int i = 0; i < N; i++) {
        int v = ord[i];
        if (v == 0) eff[v] = (tr[0].nh && !dead[0]) ? tr[0].nh : 0;
        else eff[v] = (tr[v].nh && !dead[v]) ? tr[v].nh : eff[parent[v]];
    }
    // monochromatic (bottom-up)
    unsigned char *mono = (unsigned char*)malloc((size_t)N);
    unsigned *mcolor = (unsigned*)malloc((size_t)N * sizeof(unsigned));
    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) { mono[v] = 1; mcolor[v] = eff[v]; }
        else {
            unsigned h0 = 0, h1 = 0; int ok0 = 1, ok1 = 1;
            if (c0) { if (mono[c0]) h0 = mcolor[c0]; else ok0 = 0; }
            else h0 = eff[v];
            if (c1) { if (mono[c1]) h1 = mcolor[c1]; else ok1 = 0; }
            else h1 = eff[v];
            if (ok0 && ok1 && h0 == h1) { mono[v] = 1; mcolor[v] = h0; } else mono[v] = 0;
        }
    }
    out = (RoutingTableEntry*)malloc((size_t)(n + 16) * sizeof(RoutingTableEntry));
    int outcnt = 0, outcap = n + 16;
#define EMIT(e) do { \
        if (outcnt >= outcap) { outcap = outcap * 2; out = (RoutingTableEntry*)realloc(out, (size_t)outcap * sizeof(RoutingTableEntry)); } \
        out[outcnt++] = (e); \
    } while (0)
    for (int v = 0; v < N; v++) {
        unsigned peff = (parent[v] < 0) ? 0u : eff[parent[v]];
        int live = (tr[v].nh != 0) && !dead[v];
        if (mono[v]) {
            if (mcolor[v] != 0 && mcolor[v] != peff && !(parent[v] >= 0 && mono[parent[v]])) {
                RoutingTableEntry e;
                e.addr = __builtin_bswap32(ipv[v] << (32 - lenv[v]));
                e.len = lenv[v];
                e.nexthop = mcolor[v] - 1;
                e.pad[0] = e.pad[1] = e.pad[2] = 0;
                EMIT(e);
            }
        } else if (live && eff[v] != peff) {
            RoutingTableEntry e;
            e.addr = __builtin_bswap32(ipv[v] << (32 - lenv[v]));
            e.len = lenv[v];
            e.nexthop = eff[v] - 1;
            e.pad[0] = e.pad[1] = e.pad[2] = 0;
            EMIT(e);
        }
    }
#undef EMIT
    free(parent); free(eff); free(ipv); free(lenv); free(stack); free(ord);
    free(below); free(coveredBelow); free(dead); free(mono); free(mcolor); free(tr);
    qsort(out, outcnt, sizeof(RoutingTableEntry), cmpEntry);
    *tbl_comp = out;
    *n_comp = outcnt;
}

评测结果