代码

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

static unsigned *l1;      // 65536 entries
static unsigned char *l1deep; // 65536
static unsigned *l2;      // nd16 * 256
static unsigned char *l2deep; // nd16 * 256
static unsigned *l3;      // nd24 * 256

void init(int n, int q, const RoutingTableEntry *a) {
    l1 = (unsigned*)malloc(65536 * sizeof(unsigned));
    l1deep = (unsigned char*)calloc(65536, 1);

    // find default route /0
    unsigned defnh = 0;
    if (a[0].len == 0 && __builtin_bswap32(a[0].addr) == 0) defnh = a[0].nexthop;
    // init l1 to default
    for (int i = 0; i < 65536; i++) l1[i] = defnh;

    // pass 1: paint len<=16 into l1, count deep /16 and /24
    int nd16 = 0, nd24 = 0;
    unsigned last16 = 0xFFFFFFFFu, last24 = 0xFFFFFFFFu;
    for (int i = 0; i < n; i++) {
        unsigned ip = __builtin_bswap32(a[i].addr);
        int len = a[i].len;
        unsigned nh = a[i].nexthop;
        if (len <= 16) {
            unsigned p = ip >> 16;
            unsigned cnt = 1u << (16 - len);
            for (unsigned j = 0; j < cnt; j++) l1[p + j] = nh;
        } else {
            unsigned p = ip >> 16;
            if (p != last16) { nd16++; last16 = p; }
            if (len > 24) { unsigned x = ip >> 8; if (x != last24) { nd24++; last24 = x; } }
        }
    }

    l2 = (unsigned*)malloc((size_t)nd16 * 256 * sizeof(unsigned));
    l2deep = (unsigned char*)calloc((size_t)nd16 * 256, 1);
    l3 = (unsigned*)malloc((size_t)nd24 * 256 * sizeof(unsigned));

    // pass 2: paint len>16 into l2/l3
    unsigned l2cnt = 0, l3cnt = 0;
    for (int i = 0; i < n; i++) {
        unsigned ip = __builtin_bswap32(a[i].addr);
        int len = a[i].len;
        unsigned nh = a[i].nexthop;
        if (len <= 16) continue;
        unsigned p = ip >> 16;
        unsigned bidx; // l2 block index
        if (l1deep[p] == 0) {
            l1deep[p] = 1;
            unsigned nh16 = l1[p];
            bidx = l2cnt++;
            l1[p] = bidx;
            // init block to nh16
            for (int j = 0; j < 256; j++) l2[(bidx << 8) | j] = nh16;
        } else {
            bidx = l1[p];
        }
        if (len <= 24) {
            unsigned s = (ip >> 8) & 0xFFu;
            unsigned cnt = 1u << (24 - len);
            for (unsigned j = 0; j < cnt; j++) l2[(bidx << 8) | (s + j)] = nh;
        } else {
            unsigned x24 = (ip >> 8) & 0xFFu;
            unsigned li = (bidx << 8) | x24; // l2 index
            unsigned tidx; // l3 block index
            if (l2deep[li] == 0) {
                l2deep[li] = 1;
                unsigned nh24 = l2[li];
                tidx = l3cnt++;
                l2[li] = tidx;
                for (int j = 0; j < 256; j++) l3[(tidx << 8) | j] = nh24;
            } else {
                tidx = l2[li];
            }
            unsigned s = ip & 0xFFu;
            unsigned cnt = 1u << (32 - len);
            for (unsigned j = 0; j < cnt; j++) l3[(tidx << 8) | (s + j)] = nh;
        }
    }
}

unsigned query(unsigned addr) {
    unsigned ip = __builtin_bswap32(addr);
    unsigned p = ip >> 16;
    unsigned v = l1[p];
    if (__builtin_expect(l1deep[p], 0)) {
        unsigned idx = (v << 8) | ((ip >> 8) & 0xFFu);
        v = l2[idx];
        if (__builtin_expect(l2deep[idx], 0)) {
            v = l3[(v << 8) | (ip & 0xFFu)];
        }
    }
    return v;
}

评测结果