代码

// This code is AI-generated. (AI 生成的代码)
// router32: longest-prefix-match for a BGP table.
//
// A 16/8/8 multibit trie.  Level 1 maps the top 16 bits; levels 2 and 3 are
// 256-entry tables for the next 8 and last 8 bits.  The level-2/3 tables are
// run-length compressed into (bitmask, prefix-sum, pointer) triples, so a query
// touches only a few cache-friendly arrays; popcount over the 32-bit run mask
// locates the entry.
//
// The input is sorted by address, so init builds each /16 block in a small
// on-stack level-2 table, compresses it immediately and reuses the buffer.
// This keeps the working set in L1/L2 instead of touching 48 MB of raw tables.
#include "router.h"
#include <arpa/inet.h>
#include <stdint.h>
#include <string.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt")

typedef uint16_t u16;
typedef uint32_t u32;

enum { N24 = 65536, N32 = 32768, L2_RUNS = 4u << 20, L3_RUNS = 2u << 20 };

struct LvPack { u32 bits, sum; };

static u32 t16[65536];
static u16 l2_ptr[L2_RUNS];
static u32 l2_run_cnt;
static LvPack l2[N24][8];
static u16 l3_ptr[L3_RUNS];
static u32 l3_run_cnt;
static LvPack l3[N32][8];
static u32 n24_cnt, n32_cnt;

static u32 loc24[256];
static u32 loc32[256][256];
static u16 loc32_idx[256];

static u32 nh_key[1 << 17];
static u16 nh_val[1 << 17];
static u32 nh[1 << 16];
static u32 nh_count = 1;

static u16 intern(u32 x) {
    u32 h = (x * 2654435761u) >> 15;
    while (nh_key[h] && nh_key[h] != x + 1) h = (h + 1) & 0x1ffffu;
    if (nh_key[h]) return nh_val[h];
    nh_key[h] = x + 1;
    nh_val[h] = (u16)nh_count;
    nh[nh_count] = x;
    return (u16)nh_count++;
}

static inline void fill16(u32 *d, u32 cnt, u32 v) {
    for (u32 i = 0; i < cnt; ++i) d[i] = v;
}
static inline void fill32(u32 *d, u32 cnt, u32 v) {
    for (u32 i = 0; i < cnt; ++i) d[i] = v;
}

// keep the compiler from eliminating the scratch writes
static void compress24(void);
static void compress32(u32 idx, const u32 *tab);
static int cur_top = -1;

static void finalize(void) {
    if (cur_top < 0) return;
    compress24();
    for (int mid = 0; mid < 256; ++mid)
        if (loc32_idx[mid] != 0xffff) compress32(loc32_idx[mid], loc32[mid]);
    cur_top = -1;
}

static void compress24(void) {
    u32 idx = n24_cnt++;
    u16 *p = l2_ptr + l2_run_cnt;
    u16 cur = (loc24[0] >> 31) ? (u16)(0x8000 | (loc24[0] & 0x7fff)) : (u16)loc24[0];
    u32 cnt = 0;
    p[0] = cur;
    l2[idx][0].sum = l2_run_cnt;
    for (u32 i = 1; i < 256; ++i) {
        if ((i & 31) == 0) l2[idx][i >> 5].sum = l2_run_cnt + cnt;
        u16 e = (loc24[i] >> 31) ? (u16)(0x8000 | (loc24[i] & 0x7fff)) : (u16)loc24[i];
        if (e != cur) { l2[idx][i >> 5].bits |= 1u << (i & 31); cur = e; p[++cnt] = e; }
    }
    l2_run_cnt += cnt + 1;
    t16[cur_top] = 0x80000000u | idx;
}

static void compress32(u32 idx, const u32 *tab) {
    u16 *p = l3_ptr + l3_run_cnt;
    u16 cur = (u16)tab[0];
    u32 cnt = 0;
    p[0] = cur;
    l3[idx][0].sum = l3_run_cnt;
    for (u32 i = 1; i < 256; ++i) {
        if ((i & 31) == 0) l3[idx][i >> 5].sum = l3_run_cnt + cnt;
        u16 e = (u16)tab[i];
        if (e != cur) { l3[idx][i >> 5].bits |= 1u << (i & 31); cur = e; p[++cnt] = e; }
    }
    l3_run_cnt += cnt + 1;
}

void init(int n, int q, const RoutingTableEntry *tbl) {
    (void)q;
    memset(t16, 0, sizeof(t16));
    n24_cnt = n32_cnt = 0;
    l2_run_cnt = l3_run_cnt = 0;
    nh_count = 1;
    cur_top = -1;

    for (int i = 0; i < n; ++i) {
        u32 addr = htonl(tbl[i].addr);
        u32 len = tbl[i].len;
        u32 id = intern(tbl[i].nexthop);
        if (len <= 16) {
            finalize();
            fill16(t16 + (addr >> 16), 1u << (16 - len), id);
            continue;
        }
        u32 top = addr >> 16;
        if (cur_top != (int)top) {
            finalize();
            cur_top = (int)top;
            u32 b = t16[top];
            fill32(loc24, 256, b);
            memset(loc32_idx, 0xff, sizeof(loc32_idx));
        }
        if (len <= 24) {
            fill32(loc24 + ((addr >> 8) & 255), 1u << (24 - len), id);
        } else {
            u32 mid = (addr >> 8) & 255;
            u32 idx32 = loc32_idx[mid];
            if (idx32 == 0xffff) {
                idx32 = n32_cnt++;
                loc32_idx[mid] = (u16)idx32;
                u32 b = loc24[mid];
                fill32(loc32[mid], 256, b & 0x7fffffffu);
                loc24[mid] = 0x80000000u | idx32;
            }
            fill32(loc32[mid] + (addr & 255), 1u << (32 - len), id);
        }
    }
    finalize();
}

unsigned query(unsigned addr_raw) {
    u32 addr = htonl(addr_raw);
    u32 v = t16[addr >> 16];
    if (v & 0x80000000u) {
        u32 idx = v & 0x7fffffffu;
        u32 a = (addr >> 8) & 255;
        u32 chunk = a >> 5;
        u32 off = l2[idx][chunk].sum + __builtin_popcount(l2[idx][chunk].bits & ((2u << (a & 31)) - 1));
        u16 e = l2_ptr[off];
        if (e & 0x8000) {
            u32 idx2 = e & 0x7fff;
            u32 a2 = addr & 255;
            u32 chunk2 = a2 >> 5;
            u32 off2 = l3[idx2][chunk2].sum + __builtin_popcount(l3[idx2][chunk2].bits & ((2u << (a2 & 31)) - 1));
            return nh[l3_ptr[off2]];
        }
        return nh[e];
    }
    return nh[v];
}

评测结果