代码

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

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

static unsigned nh_table[256];
static unsigned char htab[256];

void init(int n, int q, const RoutingTableEntry *a) {
    l1 = (unsigned short*)calloc(65536, 2);
    l1deep = (unsigned char*)calloc(65536, 1);
    memset(nh_table, 0, sizeof(nh_table));
    memset(htab, 0, sizeof(htab));

    int D = 0;
    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;
        unsigned idx;
        if (nh == 0) idx = 0;
        else {
            unsigned h = (nh * 2654435761u) >> 24;
            while (htab[h] != 0 && nh_table[htab[h]] != nh) h = (h + 1) & 255;
            if (htab[h] == 0) { htab[h] = (unsigned char)(++D); nh_table[D] = nh; }
            idx = htab[h];
        }
        if (len <= 16) {
            unsigned p = ip >> 16;
            unsigned cnt = 1u << (16 - len);
            for (unsigned j = 0; j < cnt; j++) l1[p + j] = (unsigned short)idx;
        } 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 short*)malloc((size_t)nd20 * 16 * sizeof(unsigned short));
    l3deep = (unsigned char*)calloc((size_t)nd20 * 16, 1);
    l4 = (unsigned short*)malloc((size_t)nd24 * 256 * sizeof(unsigned short));

    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 idx;
        if (nh == 0) idx = 0;
        else {
            unsigned h = (nh * 2654435761u) >> 24;
            while (htab[h] != 0 && nh_table[htab[h]] != nh) h = (h + 1) & 255;
            idx = htab[h];
        }
        unsigned p = ip >> 16;
        unsigned b2;
        if (l1deep[p] == 0) {
            l1deep[p] = 1;
            unsigned short nh16 = l1[p];
            b2 = l2cnt++;
            l1[p] = (unsigned short)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)] = idx;
        } 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] = (unsigned short)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)] = (unsigned short)idx;
            } else {
                unsigned li3 = (b3 << 4) | ((ip >> 8) & 0xFu);
                unsigned b4;
                if (l3deep[li3] == 0) {
                    l3deep[li3] = 1;
                    unsigned short nh24 = l3[li3];
                    b4 = l4cnt++;
                    l3[li3] = (unsigned short)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)] = (unsigned short)idx;
            }
        }
    }
}

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 nh_table[v];
}

评测结果