代码

#include "router.h"

typedef struct {
  RoutingTableEntry entry;
  int next[2];
} TrieNode;

TrieNode trie[30000000];
int trie_index = 0;

void update(RoutingTableEntry entry) {
  if (entry.addr == 0 && entry.len == 0) {
    trie[0].entry.len = 1;
    trie[0].entry.nexthop = entry.nexthop;
    return;
  }

  int ptr = 0;
  for (int i = 0; i < entry.len; i++) {
    int b = (entry.addr >> i) & 0x1;
    if (trie[ptr].next[b] == 0) {
      trie[ptr].next[b] = ++trie_index;
      ptr = trie_index;
      trie[ptr].entry.addr = entry.addr & ((1 << (i + 1)) - 1);
    } else {
      ptr = trie[ptr].next[b];
    }
  }
  trie[ptr].entry.len = entry.len;
  trie[ptr].entry.nexthop = entry.nexthop;
}

void init(int n, int q, const RoutingTableEntry *a) {
  for (int i = 0; i < n; i++) {
    update(a[i]);
  }
}

unsigned query(unsigned addr) {
  unsigned nexthop = 0;
  if (addr == 0 && trie[0].entry.len == 1) {
    nexthop = trie[0].entry.nexthop;
  }

  int ptr = 0;
  for (int i = 0; i < 32; i++) {
    int b = (addr >> i) & 0x1;
    if (trie[ptr].next[b] == 0) {
      break;
    }
    ptr = trie[ptr].next[b];
    if (trie[ptr].entry.len != 0) {
      nexthop = trie[ptr].entry.nexthop;
    }
  }

  return nexthop;
}

评测结果