代码

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

void copyEntry(RoutingTableEntry * entry, RoutingTableEntry oldEntry) {
  entry -> addr = oldEntry.addr;
  entry -> len = oldEntry.len;
  entry -> pad[0] = oldEntry.pad[0];
  entry -> pad[1] = oldEntry.pad[1];
  entry -> pad[2] = oldEntry.pad[2];
  entry -> nexthop = oldEntry.nexthop;
}

struct Node {
  RoutingTableEntry * entry = nullptr;
  Node * parent = nullptr;
  Node * lNode = nullptr, * rNode = nullptr;
};

class RoutingTrie {
  static Node * root;
public:
  static RoutingTableEntry * search(unsigned addr) {
    addr = ntohl(addr);
    Node * node = root;
    RoutingTableEntry * entry = nullptr;
    for (int i = 0; i < 32; i ++) {
      int bit = addr >> 31;
      node = (bit == 0) ? node -> lNode : node -> rNode;
      if (node != nullptr) {
        entry = (node -> entry == nullptr) ? entry : node -> entry; 
      } else {
        break;
      }
      addr = addr << 1;
    }
    return entry;
  }

  static void insertNode(RoutingTableEntry entry) {
    unsigned addr = ntohl(entry.addr);
    int len = entry.len - '0';
    Node * node = root;
    for (int i = 0; i < len; i ++) {
      int bit = addr >> 31;
      if (bit == 0) {
        if (node -> lNode == nullptr) {
          node -> lNode = new Node;
          node -> lNode -> parent = node;
        }
        node = node -> lNode;
      } else {
        if (node -> rNode == nullptr) {
          node -> rNode = new Node;
          node -> rNode -> parent = node;
        }
        node = node -> rNode;
      }
      addr = addr << 1;
    }
    if (node -> entry != nullptr) {
      if (node -> entry -> addr == entry.addr) {
        copyEntry(node -> entry, entry);
      }
    } else {
      node -> entry = new RoutingTableEntry;
      copyEntry(node -> entry, entry);
    }
  }
};

Node * RoutingTrie::root = new Node;

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

unsigned query(unsigned addr) {
  RoutingTableEntry * entry = RoutingTrie::search(addr);
  if (entry != nullptr) {
    return entry -> nexthop;
  }
  return 0;
}

评测结果