代码

/* 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;

#define MAXE 2000000

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 = tbl[i - 1].addr, ca = 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[(src[i].addr >> sh) & 255u]++;
            if (cnt[(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 = 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; }

    static u64 s_end[64];
    static u32 s_nh[64];
    int sp = 0, cnt2 = 0;
    for (int i = 0; i < n; i++) {
        u32 addr = 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 = addr; width = 1; }
        else {
            u32 mask = (u32)((1ULL << (32 - len)) - 1);
            base = addr & ~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_nh[sp - 1] : 0u;
        if (nh != inh) {
            out[cnt2].addr = 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_nh[sp] = nh;
        sp++;
    }
    free(buf);
    static RoutingTableEntry dummy; dummy.addr=0; dummy.len=0; dummy.pad[0]=dummy.pad[1]=dummy.pad[2]=0; dummy.nexthop=0;
    (void)out; (void)cnt2;
    *tbl_comp = &dummy;
    *n_comp = 0;
}

评测结果