代码

#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 *parent;
static unsigned *ipv;
static unsigned char *lenv;

static unsigned *vals;
static int D;
static unsigned char htab[128];

static unsigned long long *S;
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 cmpUnsigned(const void *x, const void *y) {
    unsigned a = *(const unsigned*)x, b = *(const unsigned*)y;
    return a < b ? -1 : (a > b ? 1 : 0);
}

// stable counting sort by len
static void sortByLen(RoutingTableEntry *a, int n, RoutingTableEntry *tmp) {
    int cnt[33]; memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; i++) cnt[a[i].len]++;
    int acc = 0;
    for (int i = 0; i <= 32; i++) { int t = cnt[i]; cnt[i] = acc; acc += t; }
    for (int i = 0; i < n; i++) tmp[cnt[a[i].len]++] = a[i];
    memcpy(a, tmp, (size_t)n * sizeof(RoutingTableEntry));
}

// LSD radix sort by 32-bit ip (bswap(addr)); stable
static void radixByIp(RoutingTableEntry *a, int n, RoutingTableEntry *tmp) {
    int cnt[256];
    for (int shift = 0; shift < 32; shift += 8) {
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; i++) cnt[(__builtin_bswap32(a[i].addr) >> shift) & 255]++;
        int acc = 0;
        for (int i = 0; i < 256; i++) { int t = cnt[i]; cnt[i] = acc; acc += t; }
        for (int i = 0; i < n; i++) { int d = (__builtin_bswap32(a[i].addr) >> shift) & 255; tmp[cnt[d]++] = a[i]; }
        RoutingTableEntry *sw = a; a = tmp; tmp = sw;
    }
}

// LSD radix sort by raw addr
static void radixByAddr(RoutingTableEntry *a, int n, RoutingTableEntry *tmp) {
    int cnt[256];
    for (int shift = 0; shift < 32; shift += 8) {
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; i++) cnt[(a[i].addr >> shift) & 255]++;
        int acc = 0;
        for (int i = 0; i < 256; i++) { int t = cnt[i]; cnt[i] = acc; acc += t; }
        for (int i = 0; i < n; i++) { int d = (a[i].addr >> shift) & 255; tmp[cnt[d]++] = a[i]; }
        RoutingTableEntry *sw = a; a = tmp; tmp = sw;
    }
}

void compress(const RoutingTableEntry *tbl, int n, RoutingTableEntry **tbl_comp, int *n_comp) {
    RoutingTableEntry *ta = (RoutingTableEntry*)malloc((size_t)n * sizeof(RoutingTableEntry));
    RoutingTableEntry *tatmp = (RoutingTableEntry*)malloc((size_t)n * sizeof(RoutingTableEntry));
    memcpy(ta, tbl, (size_t)n * sizeof(RoutingTableEntry));
    sortByLen(ta, n, tatmp);       // stable by len
    radixByIp(ta, n, tatmp);       // stable by ip -> (ip, len)

    size_t maxn = (size_t)n * 33 + 2;
    tr = (Node*)malloc(maxn * sizeof(Node));
    parent = (int*)malloc(maxn * sizeof(int));
    ipv = (unsigned*)malloc(maxn * sizeof(unsigned));
    lenv = (unsigned char*)malloc(maxn);

    cnt = 0;
    tr[0].c0 = tr[0].c1 = 0; tr[0].nh = 0;
    parent[0] = -1; ipv[0] = 0; lenv[0] = 0;
    cnt = 1;
    int *stk = (int*)malloc(34 * sizeof(int));
    stk[0] = 0;
    int sd = 0;
    unsigned prev_ip = 0; int prev_len = 0; int first = 1;
    for (int i = 0; i < n; i++) {
        unsigned ip = __builtin_bswap32(ta[i].addr);
        int len = ta[i].len;
        unsigned h = ta[i].nexthop;
        int common;
        if (first) { common = 0; first = 0; }
        else {
            int lcp = __builtin_clz(prev_ip ^ ip);
            common = lcp < prev_len ? lcp : prev_len;
            common = common < len ? common : len;
        }
        while (sd > common) sd--;
        int node = stk[sd];
        for (int d = common; d < len; d++) {
            int bit = (ip >> (31 - d)) & 1;
            int nn = cnt++;
            tr[nn].c0 = tr[nn].c1 = 0; tr[nn].nh = 0;
            if (bit) tr[node].c1 = nn; else tr[node].c0 = nn;
            parent[nn] = node;
            ipv[nn] = (ipv[node] << 1) | (unsigned)bit;
            lenv[nn] = (unsigned char)(d + 1);
            stk[++sd] = nn;
            node = nn;
        }
        tr[stk[sd]].nh = h + 1;
        prev_ip = ip; prev_len = len;
    }
    free(stk);
    int N = cnt;
    free(ta); free(tatmp);

    vals = (unsigned*)malloc((size_t)(N + 2) * sizeof(unsigned));
    vals[0] = 0;
    D = 1;
    memset(htab, 0, sizeof(htab));
    for (int v = 0; v < N; v++) {
        unsigned x = tr[v].nh;
        if (x == 0) continue;
        unsigned h = (x * 2654435761u) >> 25;
        while (htab[h] != 0 && vals[htab[h]] != x) h = (h + 1) & 127;
        if (htab[h] == 0) { htab[h] = (unsigned char)D; vals[D++] = x; }
    }

    int *idx_eff = (int*)malloc((size_t)N * sizeof(int));
    for (int v = 0; v < N; v++) {
        unsigned x = tr[v].nh;
        if (x != 0) {
            unsigned h = (x * 2654435761u) >> 25;
            while (htab[h] != 0 && vals[htab[h]] != x) h = (h + 1) & 127;
            idx_eff[v] = htab[h];
        } 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 = 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 {
            int base = 0;
            unsigned long long s0, s1;
            if (c0) { base += best[c0]; s0 = S[c0]; } else { s0 = 1ULL << idx_eff[v]; }
            if (c1) { base += best[c1]; s1 = S[c1]; } else { s1 = 1ULL << idx_eff[v]; }
            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;
    int *bg = (int*)malloc((size_t)N * sizeof(int));
    bg[0] = 0;
    for (int v = 0; v < N; v++) {
        int b = bg[v];
        int c0 = tr[v].c0, c1 = tr[v].c1;
        int nb;
        if ((S[v] >> b) & 1ULL) {
            nb = b;
        } else {
            int c = __builtin_ctzll(S[v]);
            if (c != 0) emitOne(ipv[v], lenv[v], vals[c] - 1);
            nb = c;
        }
        if (c1) bg[c1] = nb;
        if (c0) bg[c0] = nb;
        int ei = idx_eff[v];
        if (c0 == 0 && c1 != 0 && nb != ei) emitOne(ipv[v] << 1, lenv[v] + 1, vals[ei] - 1);
        if (c1 == 0 && c0 != 0 && nb != ei) emitOne((ipv[v] << 1) | 1u, lenv[v] + 1, vals[ei] - 1);
    }

    free(parent); free(ipv); free(lenv); free(idx_eff); free(S); free(best); free(vals); free(bg); free(tr);
    RoutingTableEntry *otmp = (RoutingTableEntry*)malloc((size_t)outcnt * sizeof(RoutingTableEntry));
    radixByAddr(out, outcnt, otmp);
    free(otmp);
    *tbl_comp = out;
    *n_comp = outcnt;
}

评测结果