代码

#include "router.h"
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

// /20 cut: A[2^20] u32 (raw nexthop, no nh_tab for shallow 87.4%) +
// full /24 u16 table (33.5MB, code + nh_tab, direct index, lazily materialized)
// + per-/24 L3 for len>=25 (rare). Deep L2[ip>>8] is direct (MLP-friendly).

static uint32_t *A;
static uint8_t  *hasDeep;
static uint16_t *L2;
static uint8_t  *L3;
static uint32_t *l3key;
static uint32_t *l3off;
static uint32_t l3cnt;

static uint32_t nh_tab[256];
static uint32_t nh_keys[256];
static uint8_t  nh_codes[256];
static uint32_t ncode_count;

static inline uint8_t nh_code(uint32_t raw){
    uint32_t h = (raw * 2654435761u) >> 24;
    for(;;){
        if (nh_codes[h] == 0){
            nh_keys[h] = raw;
            ncode_count++;
            nh_tab[ncode_count] = raw;
            nh_codes[h] = (uint8_t)ncode_count;
            return (uint8_t)ncode_count;
        }
        if (nh_keys[h] == raw) return nh_codes[h];
        h = (h + 1) & 255;
    }
}

void init(int n, int q, const RoutingTableEntry *a){
    (void)q;
    memset(nh_codes, 0, sizeof(nh_codes));
    ncode_count = 0;
    nh_tab[0] = 0;

    A = (uint32_t*)calloc(1u << 20, 4);
    hasDeep = (uint8_t*)calloc((1u << 20) >> 3, 1);
    L2 = (uint16_t*)malloc((size_t)(1u << 24) * 2);
    L3 = (uint8_t*)malloc((size_t)n * 256);
    l3key = (uint32_t*)malloc((size_t)n * 4);
    l3off = (uint32_t*)malloc((size_t)n * 4);
    l3cnt = 0;

    uint32_t l3cur = 0;

    for (int i = 0; i < n; i++) {
        uint32_t v = __builtin_bswap32(a[i].addr);
        uint32_t len = a[i].len;
        uint32_t nh = a[i].nexthop;
        if (len <= 20) {
            uint32_t shift = 20 - len;
            uint32_t count = 1u << shift;
            uint32_t mask = count - 1;
            uint32_t base = (v >> 12) & ~mask;
            uint32_t end = base | mask;
            for (uint32_t x = base; x <= end; x++) A[x] = nh;
        } else {
            uint8_t code = nh_code(nh);
            uint32_t s = v >> 12;
            uint32_t idx = s >> 3;
            uint32_t bit = 1u << (s & 7);
            if (!(hasDeep[idx] & bit)) {
                hasDeep[idx] |= bit;
                // materialize this /20's 16 /24s: fallback = A[s] -> code
                // A[s] is a raw nexthop; map to a code (append if new)
                uint8_t defc = nh_code(A[s]);
                uint32_t base24 = s << 4;
                for (uint32_t c = 0; c < 16; c++) L2[base24 + c] = defc;
            }
            uint32_t cell = (v >> 8) & 15;
            uint32_t i24 = (s << 4) + cell;
            if (len <= 24) {
                uint32_t shift = 24 - len;
                uint32_t count = 1u << shift;
                uint32_t mask = count - 1;
                uint32_t base = cell & ~mask;
                uint32_t end = base | mask;
                for (uint32_t x = base; x <= end; x++) L2[(s << 4) + x] = code;
            } else {
                uint16_t *e = &L2[i24];
                if (*e != 0xFFFF) {
                    uint32_t l3 = l3cur; l3cur += 256;
                    for (uint32_t c = 0; c < 256; c++) L3[l3 + c] = (uint8_t)*e;
                    *e = 0xFFFF;
                    l3key[l3cnt] = v >> 8;
                    l3off[l3cnt] = l3;
                    l3cnt++;
                }
                uint32_t l3 = l3off[l3cnt - 1];
                uint32_t shift = 32 - len;
                uint32_t count = 1u << shift;
                uint32_t mask = count - 1;
                uint32_t base = v & ~mask;
                uint32_t end = base | mask;
                for (uint32_t x = base; x <= end; x++) L3[l3 + (x & 255)] = code;
            }
        }
    }
}

static inline uint32_t lookup(uint32_t h){
    uint32_t s = h >> 12;
    uint32_t ans = A[s];
    if (hasDeep[s >> 3] & (1u << (s & 7))) {
        uint32_t c = L2[h >> 8];
        if (c != 0xFFFF) {
            ans = nh_tab[c];
        } else {
            uint32_t k = h >> 8;
            uint32_t lo = 0, hi = l3cnt;
            while (lo < hi) {
                uint32_t mid = (lo + hi) >> 1;
                if (l3key[mid] < k) lo = mid + 1; else hi = mid;
            }
            uint32_t cc = L3[l3off[lo] + (h & 255)];
            ans = (cc == 255) ? A[s] : nh_tab[cc];
        }
    }
    return ans;
}

unsigned query(unsigned addr){ return lookup(__builtin_bswap32(addr)); }

评测结果