代码

#include "router.h"

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

TrieNode trie[10000];
int index = 0;

void update(bool insert, RoutingTableEntry entry) {
  if (insert) {
    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] = ++index;
        ptr = 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;
  } else {
    int ptr = 0;
    for (int i = 0; i < entry.len; i++) {
      int b = (entry.addr >> i) & 0x1;
      if (trie[ptr].next[b] == 0) {
        return;
      }
      ptr = trie[ptr].next[b];
    }
    trie[ptr].entry.len = 0;
    trie[ptr].entry.nexthop = 0;
  }
}

bool prefix_query(int addr, int *nexthop) {
  int match = (trie[0].entry.len != 0) ? 0 : -1;

  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) {
      match = trie[ptr].entry.len;
      *nexthop = trie[ptr].entry.nexthop;
    }
  }

  return match >= 0;
}

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

unsigned query(unsigned addr) {
  int nexthop;
  if (!prefix_query(addr, &nexthop)) {
    return 0;
  }
  return nexthop;
}

评测结果