代码

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

// 3-level multibit trie: L1 /16 (uint32), L2 /20 (uint32), L3 /24 (uint8), L4 /32 (uint8).
// L1/L2 store raw nexthop (>= MIN_NH) for terminal, base+1 for deep, 0 for no-match.
// L3 stores code (0..46, 47=no-match) or 255=deep. L4 stores code.
static uint32_t *L1;
static uint32_t *L2;
static uint8_t  *L3;
static uint32_t *L4base;
static uint8_t  *L4;
static uint32_t nh_tab[48];
static uint32_t MIN_NH;

#define NHMAP_SIZE 128
static uint32_t nh_keys[NHMAP_SIZE];
static uint8_t  nh_codes[NHMAP_SIZE];
static uint32_t ncode_count;

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

void init(int n, int q, const RoutingTableEntry *a){
    memset(nh_codes, 0xFF, sizeof(nh_codes));
    ncode_count = 0;
    uint8_t *b16 = (uint8_t*)calloc(65536/8, 1);
    uint8_t *b20 = (uint8_t*)calloc(1048576/8, 1);
    uint8_t *b24 = (uint8_t*)calloc(16777216/8, 1);
    uint32_t D16=0, D20=0, D24=0;
    for(int i=0;i<n;i++){
        unsigned ip = __builtin_bswap32(a[i].addr);
        unsigned len = a[i].len;
        unsigned raw = a[i].nexthop;
        nh_code(raw);
        if(len > 16){
            unsigned idx = ip>>16;
            if(!((b16[idx>>3]>>(idx&7))&1)){ b16[idx>>3]|=(1u<<(idx&7)); D16++; }
        }
        if(len > 20){
            unsigned idx = ip>>12;
            if(!((b20[idx>>3]>>(idx&7))&1)){ b20[idx>>3]|=(1u<<(idx&7)); D20++; }
        }
        if(len > 24){
            unsigned idx = ip>>8;
            if(!((b24[idx>>3]>>(idx&7))&1)){ b24[idx>>3]|=(1u<<(idx&7)); D24++; }
        }
    }
    MIN_NH = 0xFFFFFFFFu;
    for(uint32_t c=0;c<ncode_count;c++) if(nh_tab[c] < MIN_NH) MIN_NH = nh_tab[c];
    free(b16); free(b20); free(b24);

    L1 = (uint32_t*)malloc(65536*4); memset(L1, 0, 65536*4);
    L2 = (uint32_t*)malloc((size_t)D16*16*4);
    L3 = (uint8_t*)malloc((size_t)D20*16);
    L4base = (uint32_t*)malloc((size_t)D20*16*4);
    L4 = (uint8_t*)malloc((size_t)D24*256);
    uint32_t l2cur=0, l3cur=0, l4cur=0;

    for(int i=0;i<n;i++){
        int len = a[i].len;
        unsigned ip = __builtin_bswap32(a[i].addr);
        unsigned raw = a[i].nexthop;
        if(len <= 16){
            unsigned hi = ip>>16;
            int shift = 16 - len;
            int count = 1 << shift;
            int mask = count - 1;
            int lo = (int)(hi & ~(unsigned)mask), hh = (int)(hi | (unsigned)mask);
            for(int x=lo;x<=hh;x++) L1[x] = raw;
        } else {
            unsigned hi = ip>>16;
            if(L1[hi] >= MIN_NH || L1[hi] == 0){
                uint32_t base = l2cur; l2cur += 16;
                uint32_t def = L1[hi];
                for(int c=0;c<16;c++) L2[base+c] = def;
                L1[hi] = base + 1;
            }
            uint32_t base = L1[hi] - 1;
            int cell = (ip>>12)&15;
            int rl = len - 16;
            if(rl <= 4){
                int count = 1 << (4-rl);
                int mask = count-1;
                int lo = cell & ~mask, hh = cell | mask;
                for(int c=lo;c<=hh;c++) L2[base+c] = raw;
            } else {
                int idx = base + cell;
                if(L2[idx] >= MIN_NH || L2[idx] == 0){
                    uint32_t b3 = l3cur; l3cur += 16;
                    uint8_t defcode = nh_code(L2[idx]);
                    for(int c=0;c<16;c++) L3[b3+c] = defcode;
                    L2[idx] = b3 + 1;
                }
                uint32_t b3 = L2[idx] - 1;
                int cell24 = (ip>>8)&15;
                int rl2 = len - 20;
                if(rl2 <= 4){
                    uint8_t code = nh_code(raw);
                    int count = 1 << (4-rl2);
                    int mask = count-1;
                    int lo = cell24 & ~mask, hh = cell24 | mask;
                    for(int c=lo;c<=hh;c++) L3[b3+c] = code;
                } else {
                    int idx3 = b3 + cell24;
                    if(L3[idx3] != 255){
                        uint8_t defcode = L3[idx3];
                        uint32_t b4 = l4cur; l4cur += 256;
                        for(int c=0;c<256;c++) L4[b4+c] = defcode;
                        L4base[idx3] = b4;
                        L3[idx3] = 255;
                    }
                    uint32_t b4 = L4base[idx3];
                    uint8_t code = nh_code(raw);
                    int cell32 = ip & 255;
                    int rl3 = len - 24;
                    int count = 1 << (8-rl3);
                    int mask = count-1;
                    int lo = cell32 & ~mask, hh = cell32 | mask;
                    for(int c=lo;c<=hh;c++) L4[b4+c] = code;
                }
            }
        }
    }
}

unsigned query(unsigned addr){
    unsigned ip = __builtin_bswap32(addr);
    unsigned e = L1[ip>>16];
    if(e >= MIN_NH) return e;
    if(e == 0) return 0;
    unsigned e2 = L2[(e-1) + ((ip>>12)&15)];
    if(e2 >= MIN_NH) return e2;
    if(e2 == 0) return 0;
    unsigned idx = (e2-1) + ((ip>>8)&15);
    unsigned c = L3[idx];
    if(c != 255) return nh_tab[c];
    return nh_tab[L4[L4base[idx] + (ip & 255)]];
}

评测结果