代码

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

typedef struct { unsigned c0, c1, nh; } Node; // nh = nexthop+1, 0 = none
static Node *tr;
static unsigned cnt;

static inline unsigned newnode(void) {
    tr[cnt].c0 = tr[cnt].c1 = tr[cnt].nh = 0;
    return cnt++;
}

void init(int n, int q, const RoutingTableEntry *a) {
    size_t maxn = (size_t)n * 33 + 2; // worst case; only created nodes are touched
    tr = (Node*)malloc(maxn * sizeof(Node));
    cnt = 0;
    newnode(); // root = node 0
    for (int i = 0; i < n; i++) {
        unsigned ip = __builtin_bswap32(a[i].addr);
        unsigned len = a[i].len;
        unsigned h = a[i].nexthop;
        unsigned node = 0;
        for (unsigned b = 0; b < len; b++) {
            unsigned bit = (ip >> (31 - b)) & 1u;
            unsigned c = bit ? tr[node].c1 : tr[node].c0;
            if (c == 0) {
                c = newnode();
                if (bit) tr[node].c1 = c; else tr[node].c0 = c;
            }
            node = c;
        }
        tr[node].nh = h + 1;
    }
}

unsigned query(unsigned addr) {
    unsigned ip = __builtin_bswap32(addr);
    unsigned node = 0, best = tr[0].nh;
    for (int b = 0; b < 32; b++) {
        unsigned bit = (ip >> (31 - b)) & 1u;
        unsigned c = bit ? tr[node].c1 : tr[node].c0;
        if (c == 0) break;
        node = c;
        unsigned h = tr[node].nh;
        if (h) best = h;
    }
    return best ? best - 1 : 0;
}

评测结果