代码

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

// ---- trie node arrays (indexed by node id = DFS preorder creation order) ----
static int *c0, *c1;             // child indices (0 = none)
static unsigned char *eff;       // effective nexthop index (0 = none)
static unsigned char *lenv;      // depth of node
static unsigned *ipv;            // right-justified prefix value (len bits in low positions)
static unsigned long long *S;    // nexthop-index bitmask set per node

// nexthop value table: vals[0]=0 (none), vals[1..D-1] = sorted distinct (nexthop+1)
static unsigned *vals;
static int D;

static int cnt;                  // node count (next free id)
static int *path;                // build stack (max depth 33)

static RoutingTableEntry *out;
static int outcnt, outcap;

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

// in-place LSD radix sort of uint64 array, 'nbytes' significant bytes (even -> in place)
static void radix_u64(unsigned long long *a, int n, int nbytes) {
    unsigned long long *tmp = (unsigned long long*)malloc((size_t)n * 8);
    unsigned cnt[256];
    unsigned long long *src = a, *dst = tmp;
    for (int shift = 0; shift < nbytes * 8; shift += 8) {
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; i++) cnt[(unsigned)(src[i] >> shift) & 255]++;
        unsigned acc = 0;
        for (int j = 0; j < 256; j++) { unsigned c = cnt[j]; cnt[j] = acc; acc += c; }
        for (int i = 0; i < n; i++) dst[cnt[(unsigned)(src[i] >> shift) & 255]++] = src[i];
        unsigned long long *t = src; src = dst; dst = t;
    }
    if (src != a) memcpy(a, tmp, (size_t)n * 8);
    free(tmp);
}

// sort idx[] (uint32) by key[] (uint64), nbytes significant bytes
static void radix_idx_by_key(unsigned *idx, const unsigned long long *key, int n, int nbytes) {
    unsigned *tmp = (unsigned*)malloc((size_t)n * 4);
    unsigned cnt[256];
    unsigned *src = idx, *dst = tmp;
    for (int shift = 0; shift < nbytes * 8; shift += 8) {
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; i++) cnt[(unsigned)(key[src[i]] >> shift) & 255]++;
        unsigned acc = 0;
        for (int j = 0; j < 256; j++) { unsigned c = cnt[j]; cnt[j] = acc; acc += c; }
        for (int i = 0; i < n; i++) { unsigned v = src[i]; dst[cnt[(unsigned)(key[v] >> shift) & 255]++] = v; }
        unsigned *t = src; src = dst; dst = t;
    }
    if (src != idx) memcpy(idx, tmp, (size_t)n * 4);
    free(tmp);
}

// binary search enc (>=1) in vals[1..D-1] (sorted ascending); return index
static inline int nh_lookup(unsigned enc) {
    int lo = 1, hi = D - 1;
    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        unsigned v = vals[mid];
        if (v < enc) lo = mid + 1;
        else if (v > enc) hi = mid - 1;
        else return mid;
    }
    return 0;
}

void compress(const RoutingTableEntry *tbl, int n, RoutingTableEntry **tbl_comp, int *n_comp) {
    // ---- 1. collect distinct (nexthop+1) values ----
    // small open-addressing hash (enc != 0; enc = nexthop+1 is never 0 for valid data)
    unsigned *htab = (unsigned*)malloc(2048 * sizeof(unsigned));
    unsigned *ulist = (unsigned*)malloc(4096 * sizeof(unsigned));
    memset(htab, 0, 2048 * sizeof(unsigned));
    int nlist = 0;
    for (int i = 0; i < n; i++) {
        unsigned enc = tbl[i].nexthop + 1;
        unsigned h = (enc * 0x9E3779B9u) & 2047u;
        while (htab[h] != 0 && htab[h] != enc) h = (h + 1) & 2047u;
        if (htab[h] == 0) { htab[h] = enc; ulist[nlist++] = enc; }
    }
    // sort distinct values ascending (insertion sort; nlist ~ 47)
    for (int i = 1; i < nlist; i++) {
        unsigned v = ulist[i]; int j = i - 1;
        while (j >= 0 && ulist[j] > v) { ulist[j + 1] = ulist[j]; j--; }
        ulist[j + 1] = v;
    }
    D = nlist + 1;
    vals = (unsigned*)malloc((size_t)D * sizeof(unsigned));
    vals[0] = 0;
    for (int i = 0; i < nlist; i++) vals[i + 1] = ulist[i];
    free(htab); free(ulist);

    // ---- 2. build packed 64-bit keys: (ip << 14) | (len << 8) | nhidx ----
    // ip = bswap32(addr) (natural IP value, MSB = first IP bit)
    unsigned long long *key = (unsigned long long*)malloc((size_t)n * 8);
    int sorted = 1;
    unsigned prev_addr = 0; unsigned char prev_len = 0;
    for (int i = 0; i < n; i++) {
        unsigned addr = tbl[i].addr;
        unsigned char len = tbl[i].len;
        if (i > 0) {
            if (addr < prev_addr || (addr == prev_addr && len < prev_len)) sorted = 0;
        }
        prev_addr = addr; prev_len = len;
        unsigned enc = tbl[i].nexthop + 1;
        unsigned ip = __builtin_bswap32(addr);
        key[i] = ((unsigned long long)ip << 14) | ((unsigned long long)len << 8) | (unsigned long long)nh_lookup(enc);
    }
    if (!sorted) radix_u64(key, n, 6); // 48 bits significant

    // ---- 3. build binary trie (LCP-stack, cache-friendly, O(N)) ----
    size_t maxn = (size_t)n * 33 + 2;
    c0 = (int*)malloc(maxn * sizeof(int));
    c1 = (int*)malloc(maxn * sizeof(int));
    eff = (unsigned char*)malloc(maxn);
    lenv = (unsigned char*)malloc(maxn);
    ipv = (unsigned*)malloc(maxn * sizeof(unsigned));
    path = (int*)malloc(34 * sizeof(int));

    cnt = 0;
    c0[0] = c1[0] = 0; eff[0] = 0; lenv[0] = 0; ipv[0] = 0;
    cnt = 1;
    path[0] = 0;
    int sp = 1;
    unsigned prev_key = 0; int prev_klen = 0;
    for (int i = 0; i < n; i++) {
        unsigned long long kv = key[i];
        unsigned k = (unsigned)(kv >> 14);
        int l = (int)((kv >> 8) & 63);
        int ni = (int)(kv & 255);
        int lcp;
        if (i == 0) lcp = 0;
        else {
            unsigned x = k ^ prev_key;
            lcp = x ? __builtin_clz(x) : 32;
            int m = l < prev_klen ? l : prev_klen;
            if (lcp > m) lcp = m;
        }
        while (sp - 1 > lcp) sp--;
        int v = path[sp - 1];
        unsigned curv = ipv[v];
        for (int b = lcp; b < l; b++) {
            int bit = (int)((k >> (31 - b)) & 1u);
            int c = cnt++;
            c0[c] = c1[c] = 0;
            eff[c] = eff[v];
            lenv[c] = (unsigned char)(b + 1);
            ipv[c] = (curv << 1) | (unsigned)bit;
            if (bit) c1[v] = c; else c0[v] = c;
            path[sp++] = c;
            v = c;
            curv = ipv[c];
        }
        eff[v] = (unsigned char)ni;
        prev_key = k; prev_klen = l;
    }
    int N = cnt;
    free(key); free(path);

    // ---- 4. bottom-up set DP (reverse creation order = children before parents) ----
    S = (unsigned long long*)malloc((size_t)N * sizeof(unsigned long long));
    for (int v = N - 1; v >= 0; v--) {
        int c0v = c0[v], c1v = c1[v];
        unsigned ei = eff[v];
        if (c0v == 0 && c1v == 0) {
            S[v] = 1ULL << ei;
        } else {
            unsigned long long s0 = c0v ? S[c0v] : (1ULL << ei);
            unsigned long long s1 = c1v ? S[c1v] : (1ULL << ei);
            unsigned long long inter = s0 & s1;
            S[v] = inter ? inter : (s0 | s1);
        }
    }

    // ---- 5. top-down emission (forward creation order = preorder) ----
    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 c0v = c0[v], c1v = c1[v];
        int nb;
        unsigned long long sv = S[v];
        if ((sv >> b) & 1ULL) {
            nb = b;
        } else {
            int c = __builtin_ctzll(sv);
            if (c != 0) emitOne(ipv[v], lenv[v], vals[c] - 1);
            nb = c;
        }
        if (c1v) bg[c1v] = nb;
        if (c0v) bg[c0v] = nb;
        int ei = eff[v];
        if (c0v == 0 && c1v != 0 && nb != ei) emitOne(ipv[v] << 1, lenv[v] + 1, vals[ei] - 1);
        if (c1v == 0 && c0v != 0 && nb != ei) emitOne((ipv[v] << 1) | 1u, lenv[v] + 1, vals[ei] - 1);
    }

    // ---- 6. sort output by (addr, len) ascending ----
    unsigned *oidx = (unsigned*)malloc((size_t)outcnt * sizeof(unsigned));
    unsigned long long *okey = (unsigned long long*)malloc((size_t)outcnt * 8);
    for (int j = 0; j < outcnt; j++) {
        okey[j] = ((unsigned long long)out[j].addr << 6) | (unsigned long long)out[j].len;
        oidx[j] = (unsigned)j;
    }
    radix_idx_by_key(oidx, okey, outcnt, 6);
    RoutingTableEntry *out2 = (RoutingTableEntry*)malloc((size_t)outcnt * sizeof(RoutingTableEntry));
    for (int j = 0; j < outcnt; j++) out2[j] = out[oidx[j]];
    free(okey); free(oidx);
    free(out);

    *tbl_comp = out2;
    *n_comp = outcnt;
}

评测结果