代码

/* routecomp rank-1 rewrite: streaming Patricia construction + (Q,K) DP.
 *
 * Same theory/merge rules as sol/routecomp/main.cpp (verified by lab/rc/oracle.py,
 * lab/rc/xcheck.py, lab/rc/fullprof2.cpp, lab/rc/rcchk.cpp).  Differences:
 *  - no PNode array: the Patricia trie is built on a stack of open nodes while
 *    scanning the sorted entry array (trie preorder);
 *  - DP node is 24 bytes {kmask, ch0, ch1, Q|depth<<20, val|kind<<16};
 *  - DP nodes do not store a key: the reconstruction carries prefix/depth down;
 *  - empty sides allocate no node (virtual Q=0,K={A} profile, derived prefix).
 */
#include "routecomp.h"

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <time.h>
#ifdef RCTIME
static double rct0;
static double rcnow(void){struct timespec t;clock_gettime(CLOCK_PROCESS_CPUTIME_ID,&t);return t.tv_sec*1e3+t.tv_nsec/1e6;}
#define RCMARK(tag) fprintf(stderr,"  [%s] %.2f ms\n", tag, rcnow()-rct0)
#else
#define RCMARK(tag) do{}while(0)
#endif

typedef unsigned int u32;
typedef unsigned char u8;
typedef unsigned long long u64;

struct Ent { u32 key; u32 val; u32 len; };

struct DN {                 /* 24 bytes */
    u64 kmask;              /* mask path: K mask; arena path: (koff<<32)|klen */
    int ch0, ch1;           /* -1 = virtual empty side */
    u32 key;                /* prefix key of this node */
    u32 pack;               /* Q | depth<<18 | val<<24 | kind<<30 */
};
#define DQ(n)      ((int)(dn[n].pack & 0x3FFFFu))
#define DDEPTH(n)  ((int)((dn[n].pack >> 18) & 0x3Fu))
#define DVAL(n)    ((u32)((dn[n].pack >> 24) & 0x3Fu))
#define DKIND(n)   ((int)(dn[n].pack >> 30))
#define KOFF(n)    ((int)(dn[n].kmask >> 32))
#define KLEN(n)    ((int)(dn[n].kmask & 0xFFFFFFFFu))

static Ent *ent;
static DN  *dn; static int dtop, dpcap;
static u32 *karena; static long ktop, kcap;
static u32 *valof; static int nval;
static int useMask;
static RoutingTableEntry *OUT; static int OUTC;

static int kgrow(long need) {
    if (ktop + need <= kcap) return 0;
    while (ktop + need > kcap) kcap = kcap ? kcap * 2 : (1 << 16);
    u32 *nw = (u32 *)realloc(karena, (size_t)kcap * sizeof(u32));
    if (!nw) return -1;
    karena = nw;
    return 0;
}
static int kmember(int off, int len, u32 c) {
    int lo = off, hi = off + len;
    while (lo < hi) { int m = (lo + hi) >> 1; if (karena[m] < c) lo = m + 1; else hi = m; }
    return lo < off + len && karena[lo] == c;
}
static int kmerge(int ao, int alen, int bo, int blen, int *roff, int *rlen, u32 *pcommon) {
    int i = 0, j = 0, meet = 0;
    while (i < alen && j < blen) {
        u32 a = karena[ao + i], b = karena[bo + j];
        if (a == b) { meet = 1; break; }
        if (a < b) i++; else j++;
    }
    long need = meet ? (alen < blen ? alen : blen) : (long)alen + blen;
    if (kgrow(need) < 0) { *roff = ao; *rlen = alen; *pcommon = karena[ao]; return meet; }
    int off = (int)ktop;
    i = j = 0;
    if (meet) {
        while (i < alen && j < blen) {
            u32 a = karena[ao + i], b = karena[bo + j];
            if (a == b) { karena[ktop++] = a; *pcommon = a; i++; j++; }
            else if (a < b) i++; else j++;
        }
    } else {
        while (i < alen && j < blen) {
            u32 a = karena[ao + i], b = karena[bo + j];
            if (a < b) karena[ktop++] = a, i++;
            else if (b < a) karena[ktop++] = b, j++;
            else { karena[ktop++] = a; i++; j++; }
        }
        while (i < alen) karena[ktop++] = karena[ao + i++];
        while (j < blen) karena[ktop++] = karena[bo + j++];
        *pcommon = karena[off];
    }
    *roff = off; *rlen = (int)ktop - off;
    return meet;
}
static void dnGrow(void) {                     /* cold: never taken once the pool is sized right */
    dpcap = dpcap ? dpcap * 2 : 8192;
    DN *nw = (DN *)realloc(dn, (size_t)dpcap * sizeof(DN));
    if (nw) dn = nw;
}
__attribute__((always_inline)) static inline int newDN(int kind, int depth, int Q, u32 val, u32 key) {
    if (__builtin_expect(dtop == dpcap, 0)) dnGrow();
    DN *d = &dn[dtop];
    d->ch0 = -1; d->ch1 = -1; d->kmask = 0;
    d->pack = ((u32)Q & 0x3FFFFu) | ((u32)depth << 18) | ((val & 0x3Fu) << 24) | ((u32)kind << 30);
    d->key = key;
    return dtop++;
}
static void setK1(int node, u32 c) {
    if (useMask) dn[node].kmask = 1ull << c;
    else { if (kgrow(1) == 0) { dn[node].kmask = ((u64)ktop << 32) | 1u; karena[ktop++] = c; } }
}
static int kmem(int node, u32 c) {
    if (useMask) return (int)((dn[node].kmask >> c) & 1ull);
    return kmember(KOFF(node), KLEN(node), c);
}
#ifdef RCDEBUG2
static void dbgDump(void) {
    fprintf(stderr, "--- D-nodes (dtop=%d) ---\n", dtop);
    for (int i = 0; i < dtop; i++)
        fprintf(stderr, "D%d kind=%d d=%d key=%08x Q=%d val=%u K=%016llx ch=(%d,%d)\n",
                i, DKIND(i), DDEPTH(i), dn[i].key, DQ(i), DVAL(i),
                (unsigned long long)dn[i].kmask, dn[i].ch0, dn[i].ch1);
}
#endif
static void emitEntry(u32 key, int depth, u32 color) {
#ifdef RCDEBUG2
    fprintf(stderr, "  emit %08x/%d val=%u\n", key, depth, valof[color]);
#endif
    RoutingTableEntry *o = &OUT[OUTC++];
    o->addr = __builtin_bswap32(key);
    o->len = (unsigned char)depth;
    o->pad[0] = o->pad[1] = o->pad[2] = 0;
    o->nexthop = valof[color];
}

/* merge two child profiles; n<0 means a virtual (Q=0, K={virt}) side */
static int mergeSides(int n0, u32 virt0, int n1, u32 virt1, int depth, u32 A, u32 key) {
    u32 common;
    int Q0 = (n0 < 0) ? 0 : DQ(n0);
    int Q1 = (n1 < 0) ? 0 : DQ(n1);
    if (useMask) {
        u64 a = (n0 < 0) ? (1ull << virt0) : dn[n0].kmask;
        u64 b = (n1 < 0) ? (1ull << virt1) : dn[n1].kmask;
        u64 inter = a & b;
        int Q = inter ? (Q0 + Q1) : (Q0 + Q1 + 1);
        common = (u32)__builtin_ctzll(inter ? inter : (a | b));
        int me = newDN(1, depth, Q, A, key);
        dn[me].kmask = inter ? inter : (a | b);
        dn[me].ch0 = n0; dn[me].ch1 = n1;
        return me;
    } else {
        int aoff, alen, boff, blen;
        if (n0 < 0) { if (kgrow(1) < 0) return -1; aoff = (int)ktop; karena[ktop++] = virt0; alen = 1; }
        else { aoff = KOFF(n0); alen = KLEN(n0); }
        if (n1 < 0) { if (kgrow(1) < 0) return -1; boff = (int)ktop; karena[ktop++] = virt1; blen = 1; }
        else { boff = KOFF(n1); blen = KLEN(n1); }
        int off, len;
        int meet = kmerge(aoff, alen, boff, blen, &off, &len, &common);
        int Q = Q0 + Q1 + (meet ? 0 : 1);
        int me = newDN(1, depth, Q, A, key);
        dn[me].kmask = ((u64)off << 32) | (u32)len;
        dn[me].ch0 = n0; dn[me].ch1 = n1;
        return me;
    }
}

struct SE {
    u32 key, val, sa;
    int cd0, cd1;
    u32 ckey0, ckey1;       /* full key of each child (the 2 gap bits are derived lazily) */
    u8 cdep0, cdep1;
    u64 vset;               /* OR of colour masks below (mask path) */
    u32 usame;              /* colour if the whole subtree is uniform, else ~0u */
    u8 depth, marked;
};
static inline u32 seAmb(const SE &s) { return s.marked ? s.val : s.sa; }

static int closeNode(const SE &u, u64 *vsetOut, u32 *usameOut) {
    u64 own = u.marked ? (1ull << u.val) : 0ull;
    u64 cv = u.vset;
    *vsetOut = cv | own;
    int uniform;
    if (useMask) { uniform = u.marked && ((cv & ~own) == 0); *usameOut = ~0u; }
    else { uniform = u.marked && (u.usame == u.val); *usameOut = (u.usame == u.val && u.marked) ? u.val : ~0u; }
    if (uniform) {
        int lf = newDN(0, u.depth, 0, u.val, u.key);
        setK1(lf, u.val);
        return lf;
    }
    u32 A = seAmb(u);
    if (u.cd0 >= 0 && u.cd1 >= 0 && u.cdep0 == (u8)(u.depth + 1) && u.cdep1 == (u8)(u.depth + 1))
        return mergeSides(u.cd0, 0, u.cd1, 0, u.depth, A, u.key);   /* dominant case: no chain, no empty side */
    int side[2];
    u32 svirt[2];
    for (int b = 0; b < 2; b++) {
        int c = b ? u.cd1 : u.cd0;
        u32 ck = u.depth >= 32 ? u.key : (u.key | ((u32)b << (31 - u.depth)));
        int cd = (int)u.depth + 1;
        if (c < 0) { side[b] = -1; svirt[b] = A; continue; }
        int cdep = b ? u.cdep1 : u.cdep0;
        if (cdep > cd) {
            int k = cdep - cd;
            if (k == 1) {
                u32 ck2 = b ? u.ckey1 : u.ckey0;
                int db = (cd >= 32) ? 0 : (int)((ck2 >> (31 - cd)) & 1u);   /* child's key bit at depth cd */
                u32 gapkey = ck | ((u32)(1 - db) << (31 - cd));
                int gap = newDN(0, cd + 1, 0, A, gapkey);
                setK1(gap, A);
                side[b] = mergeSides(gap, 0, c, 0, cd, A, ck);
            } else {
                int Q = DQ(c) + (kmem(c, A) ? 0 : 1);
                int ch = newDN(2, cd, Q, A, ck);
                setK1(ch, A);
                dn[ch].ch0 = c;
                side[b] = ch;
            }
        } else side[b] = c;
    }
    if (!useMask) {
        /* arena path: materialise empty sides (rare) */
        for (int b = 0; b < 2; b++)
            if (side[b] < 0) {
                int lf = newDN(0, (int)u.depth + 1, 0, A, u.key);
                setK1(lf, A);
                side[b] = lf;
            }
    }
    return mergeSides(side[0], svirt[0], side[1], svirt[1], u.depth, A, u.key);
}

static int lcpLen(u32 a, u32 la, u32 b, u32 lb) {
    u32 l = la < lb ? la : lb;
    u32 m = (l == 0) ? 0xffffffffu : (l >= 32 ? 0u : ((1u << (32 - l)) - 1u));
    u32 d = (a ^ b) & ~m;
    if (!d) return (int)l;
    return __builtin_clz(d);
}

/* Reconstruction in DP-pool order: the pool is postorder (children are
   allocated before their parent), so iterating backwards processes every parent
   before its children and needs no recursion.  An explicit ambient array keeps
   the walk sequential; the emission order does not matter (the checker only
   requires LPE equivalence). */
static u32 *ambArr;
static void emitAll(int rootD) {
    if (rootD < 0) return;
    /* Explicit-stack DFS instead of the ambient array: no dtop-sized alloc/memset and
       no scattered re-read of the pool.  The stack holds (node, ambient) pairs; a DP
       tree is a trie embedding, so a few hundred slots always suffice. */
    static int sNode[512];
    static u32 sAmb[512];
    int sp = 0;
    sNode[0] = rootD; sAmb[0] = 0; sp = 1;
    while (sp) {
        --sp;
        int u = sNode[sp];
        u32 amb = sAmb[sp];
        int kind = DKIND(u);
        int depth = DDEPTH(u);
        u32 key = dn[u].key;
        if (kind == 0) {
            u32 c = DVAL(u);
            if (c != amb) emitEntry(key, depth, c);
            continue;
        }
        if (kind == 2) {
            u32 a = DVAL(u);
            if (a != amb) { emitEntry(key, depth, a); amb = a; }
            int ch = dn[u].ch0;
            if (ch >= 0) { sNode[sp] = ch; sAmb[sp] = amb; sp++; }
            continue;
        }
        u64 K = dn[u].kmask;
        u32 w;
        if ((K >> amb) & 1ull) w = amb;
        else { w = (u32)__builtin_ctzll(K); emitEntry(key, depth, w); }
        int c0 = dn[u].ch0, c1 = dn[u].ch1;
        u32 A = DVAL(u);
        if (c0 < 0) { if (A != w) emitEntry(key, depth + 1, A); }
        else { sNode[sp] = c0; sAmb[sp] = w; sp++; }
        if (c1 < 0) {
            if (A != w) emitEntry(depth >= 32 ? key : (key | (1u << (31 - depth))), depth + 1, A);
        } else { sNode[sp] = c1; sAmb[sp] = w; sp++; }
    }
}

void compress(const RoutingTableEntry *tbl, int n, RoutingTableEntry **tbl_comp, int *n_comp) {
    if (n <= 0) { *tbl_comp = (RoutingTableEntry *)malloc(8); *n_comp = 0; return; }
#ifdef RCTIME
    rct0 = rcnow();
#endif
    ent = (Ent *)malloc((size_t)n * sizeof(Ent));
    Ent *tmp = (Ent *)malloc((size_t)n * sizeof(Ent));
    if (!ent || !tmp) { *tbl_comp = (RoutingTableEntry *)malloc(8); *n_comp = 0; return; }
    for (int i = 0; i < n; i++) {
        ent[i].key = __builtin_bswap32(tbl[i].addr);
        ent[i].val = tbl[i].nexthop;
        ent[i].len = tbl[i].len > 32 ? 32 : tbl[i].len;
    }
    RCMARK("build ent");
    {
        u32 *cnt = (u32 *)malloc(2048 * sizeof(u32));
        for (int pass = 0; pass < 3; pass++) {
            int sh = pass * 11;
            int bits = pass == 2 ? 10 : 11;
            u32 nb = 1u << bits, msk = nb - 1;
            memset(cnt, 0, nb * sizeof(u32));
            for (int i = 0; i < n; i++) cnt[(ent[i].key >> sh) & msk]++;
            u32 s = 0;
            for (u32 i = 0; i < nb; i++) { u32 c = cnt[i]; cnt[i] = s; s += c; }
            for (int i = 0; i < n; i++) tmp[cnt[(ent[i].key >> sh) & msk]++] = ent[i];
            Ent *t = ent; ent = tmp; tmp = t;
        }
        free(cnt);
        for (int i = 1; i < n; i++)
            if (ent[i].key == ent[i - 1].key && ent[i].len < ent[i - 1].len) {
                Ent x = ent[i];
                int j = i - 1;
                while (j >= 0 && ent[j].key == x.key && ent[j].len > x.len) { ent[j + 1] = ent[j]; j--; }
                ent[j + 1] = x;
            }
    }
    RCMARK("sort");
    free(tmp); tmp = 0;

    {
        int m = 0;
        for (int i = 0; i < n; i++) {
            u32 len = ent[i].len;
            u32 key = len == 0 ? 0u : (len >= 32 ? ent[i].key : (ent[i].key & ~((1u << (32 - len)) - 1u)));
            if (m > 0 && ent[m - 1].key == key && ent[m - 1].len == len) continue;
            ent[m].key = key; ent[m].val = ent[i].val; ent[m].len = len;
            m++;
        }
        n = m;
    }
    RCMARK("dedupe");
    {
        size_t tsize = 8;
        while (tsize < (size_t)n * 2) tsize <<= 1;
        u32 *tab = (u32 *)calloc(tsize, sizeof(u32));
        valof = (u32 *)malloc((size_t)(n + 2) * sizeof(u32));
        nval = 0;
        valof[nval++] = 0;
        u32 tmask = (u32)tsize - 1;
        for (int i = 0; i < n; i++) {
            u32 v = ent[i].val;
            if (v == 0) { ent[i].val = 0; continue; }
            u32 h = (v * 2654435761u) & tmask;
            while (tab[h] && valof[tab[h] - 1] != v) h = (h + 1) & tmask;
            if (!tab[h]) { valof[nval] = v; tab[h] = (u32)nval + 1; nval++; }
            ent[i].val = tab[h] - 1;
        }
        free(tab);
        useMask = (nval <= 64);
    }
    RCMARK("colours");
#ifdef RCDEBUG2
    fprintf(stderr, "nval=%d useMask=%d ktop=%ld\n", nval, useMask, ktop);
#endif

    /* preallocate the DP pool: at most 2n nodes, avoids realloc copying */
    dpcap = 3 * n + 64;   /* measured need ~2.17n (leaf+merge+chain nodes); 2n forced a 40MB realloc */
    dn = (DN *)malloc((size_t)dpcap * sizeof(DN));
    dtop = 0;
    karena = 0; ktop = 0; kcap = 0;
    SE st[64];
    int sp = 0;
    int start = 0;
    u32 pkey, plen;
    if (ent[0].len == 0) {
        SE r; memset(&r, 0, sizeof(r));
        r.val = ent[0].val; r.depth = 0; r.marked = 1; r.usame = ent[0].val;
        r.cd0 = r.cd1 = -1; st[sp++] = r;
        start = 1; pkey = ent[0].key; plen = ent[0].len;
    } else {
        SE r; memset(&r, 0, sizeof(r));
        r.depth = 0; r.marked = 0; r.usame = ~0u;
        r.cd0 = r.cd1 = -1; st[sp++] = r;
        pkey = 0; plen = 0;
    }
    int rootD = -1;
    for (int i = start; i < n; i++) {
        u32 key = ent[i].key, len = ent[i].len;
        int l = lcpLen(pkey, plen, key, len);
        int lastD = -1; u32 lastKey = 0; u8 lastDepth = 0; u64 lastVS = 0; u32 lastUS = ~0u;
        while (sp > 0 && (int)st[sp - 1].depth > l) {
            SE &u = st[--sp];
            u64 vs; u32 us;
            int du = closeNode(u, &vs, &us);
            if (sp > 0) {
                SE &p = st[sp - 1];
                int b = (int)((u.key >> (31 - p.depth)) & 1u);
                if (b) { p.cd1 = du; p.cdep1 = u.depth; p.ckey1 = u.key; }
                else { p.cd0 = du; p.cdep0 = u.depth; p.ckey0 = u.key; }
                p.vset |= vs;
                /* usame is only ever read on the >64-colour (arena) path, so the whole
                   bookkeeping chain is skipped in the mask path (the common case). */
                if (!useMask && (p.usame == ~0u || p.usame != us)) {
                    if (us != ~0u) { if (p.usame == ~0u) p.usame = (p.cd0 < 0 || p.cd1 < 0) ? us : ~0u; }
                    if (us == ~0u) p.usame = ~0u;
                }
            } else rootD = du;
            lastD = du; lastKey = u.key; lastDepth = u.depth; lastVS = vs; lastUS = us;
        }
        if (!(sp > 0 && (int)st[sp - 1].depth == l)) {
            SE &np = st[sp]; memset(&np, 0, sizeof(np));
            np.key = (l == 0) ? 0u : (l >= 32 ? key : (key & ~((1u << (32 - l)) - 1u)));
            np.depth = (u8)l; np.marked = 0;
            np.sa = sp > 0 ? seAmb(st[sp - 1]) : 0;
            np.cd0 = np.cd1 = -1;
            np.usame = (lastD >= 0) ? lastUS : ~0u;
            if (lastD >= 0) {
                if (sp > 0) {
                    SE &p = st[sp - 1];
                    int b = (int)((lastKey >> (31 - p.depth)) & 1u);
                    if (b) p.cd1 = -1; else p.cd0 = -1;
                }
                int b = (int)((lastKey >> (31 - np.depth)) & 1u);
                if (b) { np.cd1 = lastD; np.cdep1 = lastDepth; np.ckey1 = lastKey; }
                else { np.cd0 = lastD; np.cdep0 = lastDepth; np.ckey0 = lastKey; }
                np.vset = lastVS;
            }
            sp++;
        }
        {
            SE &np = st[sp]; memset(&np, 0, sizeof(np));
            np.key = key; np.depth = (u8)len; np.marked = 1; np.val = ent[i].val;
            np.sa = sp > 0 ? seAmb(st[sp - 1]) : 0;
            np.usame = ent[i].val;
            np.cd0 = np.cd1 = -1;
            sp++;
        }
        pkey = key; plen = len;
    }
    while (sp > 0) {
        SE &u = st[--sp];
        u64 vs; u32 us;
        int du = closeNode(u, &vs, &us);
        if (sp > 0) {
            SE &p = st[sp - 1];
            int b = (int)((u.key >> (31 - p.depth)) & 1u);
            if (b) { p.cd1 = du; p.cdep1 = u.depth; p.ckey1 = u.key; }
            else { p.cd0 = du; p.cdep0 = u.depth; p.ckey0 = u.key; }
            p.vset |= vs;
        } else rootD = du;
    }
    RCMARK("patricia+dp");
#ifdef RCDEBUG2
    dbgDump();
#endif
    OUT = (RoutingTableEntry *)malloc((size_t)(n + 8) * sizeof(RoutingTableEntry));
    OUTC = 0;
    emitAll(rootD);
    RCMARK("reconstruct");
    *tbl_comp = OUT;
    *n_comp = OUTC;
    free(ent); free(dn); free(karena); free(valof);
}

评测结果