代码

/* 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 int newDN(int kind, int depth, int Q, u32 val, u32 key) {
    if (dtop == dpcap) {
        dpcap = dpcap ? dpcap * 2 : 8192;
        DN *nw = (DN *)realloc(dn, (size_t)dpcap * sizeof(DN));
        if (nw) dn = nw;
    }
    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;
    u8 cdep0, cdep1, cbits0, cbits1;
    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);
    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);
    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) {
                int db = (int)(((b ? u.cbits1 : u.cbits0) >> 1) & 1u);
                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);
}

static void emitD(int u, u32 amb) {
    for (;;) {
        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);
            return;
        }
        if (kind == 2) {
            u32 a = DVAL(u);
            if (a != amb) { emitEntry(key, depth, a); amb = a; }
            u = dn[u].ch0;
            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 b0 = key, b1 = depth >= 32 ? key : (key | (1u << (31 - depth)));
        u32 A = DVAL(u);
        if (c0 < 0) { if (A != w) emitEntry(b0, depth + 1, A); }
        else emitD(c0, w);
        if (c1 < 0) { if (A != w) emitEntry(b1, depth + 1, A); }
        else emitD(c1, w);
        return;
    }
}

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

    dn = 0; dtop = 0; dpcap = 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.cbits1 = (u8)(((u.key >> (31 - p.depth)) & 1u) | ((p.depth >= 31) ? 0u : (((u.key >> (30 - p.depth)) & 1u) << 1))); }
                else { p.cd0 = du; p.cdep0 = u.depth; p.cbits0 = (u8)(((u.key >> (31 - p.depth)) & 1u) | ((p.depth >= 31) ? 0u : (((u.key >> (30 - p.depth)) & 1u) << 1))); }
                p.vset |= vs;
                if (p.usame == ~0u || p.usame != us) {
                    /* p's subtree uniform only if all children share the colour */
                    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; 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.cbits1 = (u8)(((lastKey >> (31 - np.depth)) & 1u) | ((np.depth >= 31) ? 0u : (((lastKey >> (30 - np.depth)) & 1u) << 1))); }
                else { np.cd0 = lastD; np.cdep0 = lastDepth; np.cbits0 = (u8)(((lastKey >> (31 - np.depth)) & 1u) | ((np.depth >= 31) ? 0u : (((lastKey >> (30 - np.depth)) & 1u) << 1))); }
                np.vset = lastVS;
            }
            st[sp++] = np;
        }
        {
            SE np; 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;
            st[sp++] = np;
        }
        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.cbits1 = (u8)(((u.key >> (31 - p.depth)) & 1u) | ((p.depth >= 31) ? 0u : (((u.key >> (30 - p.depth)) & 1u) << 1))); }
            else { p.cd0 = du; p.cdep0 = u.depth; p.cbits0 = (u8)(((u.key >> (31 - p.depth)) & 1u) | ((p.depth >= 31) ? 0u : (((u.key >> (30 - p.depth)) & 1u) << 1))); }
            p.vset |= vs;
        } else rootD = du;
    }
    RCMARK("patricia+dp");
#ifdef RCDEBUG2
    dbgDump();
#endif
    OUT = (RoutingTableEntry *)malloc((size_t)(dtop + 4) * sizeof(RoutingTableEntry));
    OUTC = 0;
    emitD(rootD, 0);
    RCMARK("reconstruct");
    *tbl_comp = OUT;
    *n_comp = OUTC;
    free(ent); free(dn); free(karena); free(valof);
}

评测结果