代码

/* Optimal routing-table compression.
 *
 * f = longest-prefix-match function of the given table.  Minimum equivalent
 * table: keep an entry iff its nexthop differs from the value inherited from the
 * nearest enclosing entry -- dropping an equal-valued entry never changes the
 * effective value seen by any deeper entry, so those drops are independent and
 * mandatory, and an entry with a different value cannot be dropped (addresses in
 * its exclusive region would resolve to the ancestor's value).
 *
 * The table need not be sorted, so sort it by (addr, len) first (stable counting
 * sort by len + 4-pass LSD radix by addr); then one stack sweep is enough. */
#include "routecomp.h"
#include <stdlib.h>
#include <string.h>

typedef unsigned u32;
typedef unsigned long long u64;

static inline u32 key_of(u32 a) { return __builtin_bswap32(a); }

void compress(const RoutingTableEntry *tbl, int n, RoutingTableEntry **tbl_comp, int *n_comp) {
    if (n <= 0) { *tbl_comp = 0; *n_comp = 0; return; }
    RoutingTableEntry *buf = (RoutingTableEntry *)malloc((size_t)n * 2 * sizeof(RoutingTableEntry) + 64);
    if (!buf) { *tbl_comp = 0; *n_comp = 0; return; }
    RoutingTableEntry *A = buf;
    RoutingTableEntry *B = buf + n;

    int sorted = 1;
    for (int i = 1; i < n; i++) {
        u32 pa = key_of(tbl[i - 1].addr), ca = key_of(tbl[i].addr);
        if (ca < pa || (ca == pa && tbl[i].len < tbl[i - 1].len)) { sorted = 0; break; }
    }
    if (sorted) {
        memcpy(A, tbl, (size_t)n * sizeof(RoutingTableEntry));
    } else {
        /* stable counting sort by len (0..32) */
        static u32 lc[40];
        memset(lc, 0, sizeof(lc));
        for (int i = 0; i < n; i++) { int L = tbl[i].len; if (L > 32) L = 32; lc[L]++; }
        { u32 s = 0; for (int i = 0; i < 40; i++) { u32 c = lc[i]; lc[i] = s; s += c; } }
        for (int i = 0; i < n; i++) { int L = tbl[i].len; if (L > 32) L = 32; B[lc[L]++] = tbl[i]; }
        /* 4-pass LSD radix sort by addr, ping-pong A<->B */
        static u32 cnt[256];
        RoutingTableEntry *src = B, *dst = A;
        for (int pass = 0; pass < 4; pass++) {
            int sh = pass << 3;
            memset(cnt, 0, sizeof(cnt));
            for (int i = 0; i < n; i++) cnt[(key_of(src[i].addr) >> sh) & 255u]++;
            if (cnt[(key_of(src[0].addr) >> sh) & 255u] == (u32)n) continue;
            u32 s = 0;
            for (int i = 0; i < 256; i++) { u32 c = cnt[i]; cnt[i] = s; s += c; }
            for (int i = 0; i < n; i++) { u32 a = key_of(src[i].addr); dst[cnt[(a >> sh) & 255u]++] = src[i]; }
            { RoutingTableEntry *t = src; src = dst; dst = t; }
        }
        if (src != A) memcpy(A, src, (size_t)n * sizeof(RoutingTableEntry));
    }

    RoutingTableEntry *out = (RoutingTableEntry *)malloc((size_t)n * sizeof(RoutingTableEntry) + 64);
    if (!out) { free(buf); *tbl_comp = 0; *n_comp = 0; return; }

    /* pass 1: covered[i] = range of entry i is fully covered by its strict descendants */
    unsigned char *covered = (unsigned char *)calloc((size_t)n, 1);
    if (!covered) { free(buf); *tbl_comp = 0; *n_comp = 0; return; }
    {
        static u64 c_end[64], c_cov[64], c_covstart[64];
        static int c_idx[64];
        int sp2 = 0;
        for (int i = 0; i < n; i++) {
            u32 addrk = key_of(A[i].addr);
            int len = (int)A[i].len;
            u32 b2; u64 w2;
            if (len <= 0) { b2 = 0; w2 = 1ULL << 32; }
            else if (len >= 32) { b2 = addrk; w2 = 1; }
            else { u32 mk = (u32)((1ULL << (32 - len)) - 1); b2 = addrk & ~mk; w2 = (u64)mk + 1; }
            u64 e2 = (u64)b2 + w2;
            while (sp2 > 0 && c_end[sp2 - 1] <= (u64)b2) {
                covered[c_idx[sp2 - 1]] = (unsigned char)(c_cov[sp2 - 1] >= c_end[sp2 - 1]);
                
                sp2--;
            }
            if (sp2 > 0) {
                /* advance parent coverage if this child starts exactly at the cursor */
                if ((u64)b2 <= c_cov[sp2 - 1] && c_cov[sp2 - 1] < e2) c_cov[sp2 - 1] = e2;
            }
            c_end[sp2] = e2; c_cov[sp2] = b2; c_covstart[sp2] = b2; c_idx[sp2] = i; sp2++;
        }
        while (sp2 > 0) {
            int ci = c_idx[sp2 - 1];
            int cvg = (c_cov[sp2 - 1] >= c_end[sp2 - 1]);
            u64 cs = c_covstart[sp2 - 1], ce = c_end[sp2 - 1];
            covered[ci] = (unsigned char)cvg;
            sp2--;
            if (sp2 > 0 && cvg && cs <= c_cov[sp2 - 1] && c_cov[sp2 - 1] < ce)
                c_cov[sp2 - 1] = ce;
        }
    }

    /* pass 2: keep entry iff its value differs from the value inherited from the
     * nearest kept ancestor AND it is not fully covered by its descendants */
    static u64 s_end[64];
    static u32 s_eff[64];
    int sp = 0, cnt2 = 0;
    for (int i = 0; i < n; i++) {
        u32 addrk = key_of(A[i].addr);
        int len = (int)A[i].len;
        u32 nh = A[i].nexthop;
        u32 base;
        u64 width;
        if (len <= 0) { base = 0; width = 1ULL << 32; }
        else if (len >= 32) { base = addrk; width = 1; }
        else {
            u32 mask = (u32)((1ULL << (32 - len)) - 1);
            base = addrk & ~mask;
            width = (u64)mask + 1;
        }
        u64 end = (u64)base + width;
        while (sp > 0 && s_end[sp - 1] <= (u64)base) sp--;
        u32 inh = (sp > 0) ? s_eff[sp - 1] : 0u;
        int keep = (nh != inh);
        if (keep) {
            out[cnt2].addr = __builtin_bswap32(base);
            out[cnt2].len = (unsigned char)len;
            out[cnt2].pad[0] = 0; out[cnt2].pad[1] = 0; out[cnt2].pad[2] = 0;
            out[cnt2].nexthop = nh;
            cnt2++;
        }
        s_end[sp] = end;
        s_eff[sp] = keep ? nh : inh;
        sp++;
    }
    free(covered);
    free(buf);
    *tbl_comp = out;
    *n_comp = cnt2;
}

评测结果