代码

#include "router.h"
#include <stdint.h>
#include <stdlib.h>
#include <arpa/inet.h>

struct Node {
  RoutingTableEntry entry;
  Node* prev;
  Node* next;
  Node() { prev = next = nullptr; }
} *root = new Node();

void update(bool insert, RoutingTableEntry entry) {
  // TODO:
  Node *cur = root;
  while (true) {
    if (cur->prev == nullptr && cur->next == nullptr)
      break;
    if (cur->entry.addr == entry.addr && cur->entry.len == entry.len) {
      if (insert)
        cur->entry = entry;
      else {
        cur->prev->next = cur->next;
        if (cur->next)
          cur->next->prev = cur->prev;
        delete cur;
      }
      break;
    }
    if (!cur->next)
      break;
    cur = cur->next;
  }
  if (!cur->next && insert) {
    cur->next = new Node();
    cur->next->entry = entry;
    cur->next->prev = cur;
  }
} 

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

unsigned query(unsigned addr) {
Node *target = nullptr;
  uint32_t maxLen = 0;
  Node *cur = root;
  while (cur) {
    if (cur->prev == nullptr) {
      cur = cur->next;
      continue;
    }
    uint32_t len = cur->entry.len;
    if (ntohl(cur->entry.addr) >> (32 - len) == ntohl(addr) >> (32 - len)) {
      if (len > maxLen) {
        target = cur;
        maxLen = len;
      }
    }
    cur = cur->next;
  }
  if (target)
    return target->entry.nexthop;
  return 0;
}

评测结果