代码

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

static unsigned *l1;       // 65536
static unsigned char *l1deep;
static unsigned *l2;       // nd16 * 16
static unsigned char *l2deep;
static unsigned *l3;       // nd20 * 16
static unsigned char *l3deep;
static unsigned *l4;       // nd24 * 256

void init(int n, int q, const RoutingTableEntry *a) {
    l1 = (unsigned*)malloc(65536 * sizeof(unsigned));
    l1deep = (unsigned char*)calloc(65536, 1);
    unsigned defnh = 0;
    if (a[0].len == 0 && __builtin_bswap32(a[0].addr) == 0) defnh = a[0].nexthop;
    for (int i = 0; i < 65536; i++) l1[i] = defnh;

    int nd16 = 0, nd20 = 0, nd24 = 0;
    unsigned last16 = 0xFFFFFFFFu, last20 = 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 > 20) { unsigned x = ip >> 12; if (x != last20) { nd20++; last20 = x; } }
            if (len > 24) { unsigned x = ip >> 8; if (x != last24) { nd24++; last24 = x; } }
        }
    }

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

    unsigned l2cnt = 0, l3cnt = 0, l4cnt = 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 b2;
        if (l1deep[p] == 0) {
            l1deep[p] = 1;
            unsigned nh16 = l1[p];
            b2 = l2cnt++;
            l1[p] = b2;
            for (int j = 0; j < 16; j++) l2[(b2 << 4) | j] = nh16;
        } else b2 = l1[p];

        if (len <= 20) {
            unsigned s = (ip >> 12) & 0xFu;
            unsigned cnt = 1u << (20 - len);
            for (unsigned j = 0; j < cnt; j++) l2[(b2 << 4) | (s + j)] = nh;
        } else {
            unsigned li2 = (b2 << 4) | ((ip >> 12) & 0xFu);
            unsigned b3;
            if (l2deep[li2] == 0) {
                l2deep[li2] = 1;
                unsigned nh20 = l2[li2];
                b3 = l3cnt++;
                l2[li2] = b3;
                for (int j = 0; j < 16; j++) l3[(b3 << 4) | j] = nh20;
            } else b3 = l2[li2];

            if (len <= 24) {
                unsigned s = (ip >> 8) & 0xFu;
                unsigned cnt = 1u << (24 - len);
                for (unsigned j = 0; j < cnt; j++) l3[(b3 << 4) | (s + j)] = nh;
            } else {
                unsigned li3 = (b3 << 4) | ((ip >> 8) & 0xFu);
                unsigned b4;
                if (l3deep[li3] == 0) {
                    l3deep[li3] = 1;
                    unsigned nh24 = l3[li3];
                    b4 = l4cnt++;
                    l3[li3] = b4;
                    for (int j = 0; j < 256; j++) l4[(b4 << 8) | j] = nh24;
                } else b4 = l3[li3];

                unsigned s = ip & 0xFFu;
                unsigned cnt = 1u << (32 - len);
                for (unsigned j = 0; j < cnt; j++) l4[(b4 << 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 i2 = (v << 4) | ((ip >> 12) & 0xFu);
        v = l2[i2];
        if (__builtin_expect(l2deep[i2], 0)) {
            unsigned i3 = (v << 4) | ((ip >> 8) & 0xFu);
            v = l3[i3];
            if (__builtin_expect(l3deep[i3], 0)) {
                v = l4[(v << 8) | (ip & 0xFFu)];
            }
        }
    }
    return v;
}

评测结果