代码

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

// /16 cut + per-slot VALIDITY bitset (no arena prefill).
//   A[65536] u32 = /16 answer (raw nexthop, L2-resident)
//   hasDeep bitset: slice has any len>=17 entry
//   O[65536] u32  : arena base = deep_ordinal*256
//   valid bitset  : (deep_ordinal*256+slot) bit set iff that /24 has a len 17-24 entry
//   arena u32     : raw nexthop, ONLY deep /24 slots written (no fallback prefill)
//   len>=25: arena slot = SENTINEL -> per-/24 L3 (binary search, ~0.025%)
// Query: shallow reads only A[s] (L2). Deep-slice reads O[s] + valid (L3),
//   and touches the DRAM arena ONLY when the slot is actually a deep entry (~4%).

#define SENTINEL 0xFFFFFFFFu

static uint32_t *A;
static uint8_t  *hasDeep;
static uint32_t *O;
static uint8_t  *valid;
static uint32_t *arena;
static uint32_t *L3;
static uint32_t *l3key;
static uint32_t *l3off;
static uint32_t l3cnt;

void init(int n, int q, const RoutingTableEntry *a){
    (void)q;
    A = (uint32_t*)calloc(65536, 4);
    hasDeep = (uint8_t*)calloc(8192, 1);
    O = (uint32_t*)malloc((size_t)65536 * 4);
    valid = (uint8_t*)calloc((size_t)65536 * 32, 1);
    arena = (uint32_t*)malloc((size_t)65536 * 256 * 4);
    L3 = (uint32_t*)malloc((size_t)n * 256 * 4);
    l3key = (uint32_t*)malloc((size_t)n * 4);
    l3off = (uint32_t*)malloc((size_t)n * 4);
    l3cnt = 0;

    uint32_t deep_ordinal = 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 <= 16) {
            uint32_t shift = 16 - len;
            uint32_t count = 1u << shift;
            uint32_t mask = count - 1;
            uint32_t base = (v >> 16) & ~mask;
            uint32_t end = base | mask;
            for (uint32_t x = base; x <= end; x++) A[x] = nh;
        } else {
            uint32_t s = v >> 16;
            uint32_t idx = s >> 3;
            uint32_t bit = 1u << (s & 7);
            uint32_t o;
            if (!(hasDeep[idx] & bit)) {
                hasDeep[idx] |= bit;
                o = deep_ordinal * 256;
                O[s] = o;
                deep_ordinal++;
            } else {
                o = O[s];
            }
            uint32_t slot = (v >> 8) & 255;
            if (len <= 24) {
                uint32_t shift = 24 - len;
                uint32_t count = 1u << shift;
                uint32_t mask = count - 1;
                uint32_t base = slot & ~mask;
                uint32_t end = base | mask;
                for (uint32_t x = base; x <= end; x++) {
                    uint32_t ii = o + x;
                    valid[ii >> 3] |= (uint8_t)(1u << (ii & 7));
                    arena[ii] = nh;
                }
            } else {
                uint32_t ii = o + slot;
                if (!((valid[ii >> 3] >> (ii & 7)) & 1)) {
                    // no len<=24 entry here: mark sentinel + L3 prefill A[s]
                    valid[ii >> 3] |= (uint8_t)(1u << (ii & 7));
                    uint32_t l3 = l3cur; l3cur += 256;
                    for (uint32_t c = 0; c < 256; c++) L3[l3 + c] = A[s];
                    arena[ii] = SENTINEL;
                    l3key[l3cnt] = v >> 8;
                    l3off[l3cnt] = l3;
                    l3cnt++;
                } else {
                    // there is a len 17-24 entry in this /24 -> replace with sentinel + L3 prefill
                    if (arena[ii] != SENTINEL) {
                        uint32_t l3 = l3cur; l3cur += 256;
                        for (uint32_t c = 0; c < 256; c++) L3[l3 + c] = arena[ii];
                        arena[ii] = SENTINEL;
                        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)] = nh;
            }
        }
    }
}

static inline uint32_t lookup(uint32_t h){
    uint32_t s = h >> 16;
    uint32_t ans = A[s];
    if (hasDeep[s >> 3] & (1u << (s & 7))) {
        uint32_t ii = O[s] + ((h >> 8) & 255);
        if ((valid[ii >> 3] >> (ii & 7)) & 1) {
            ans = arena[ii];
            if (ans == SENTINEL) {
                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;
                }
                ans = L3[l3off[lo] + (h & 255)];
            }
        }
    }
    return ans;
}

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

评测结果