代码

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

/*
  Implementation of the Routing Hash Table
*/

#define N_HLIST 1000003
#define RIP_INFINITY_BE 0x10000000

struct FibNode {
  RoutingTableEntry entry;
  FibNode* next;
};

struct FibHList {
  FibNode* first;
  FibNode* last;
};

struct FibZone {
  FibHList hlists[N_HLIST];
  unsigned prefix_len;

  /**
   * @brief Compute the hashcode of masked address
   * @param key IPv4 Address
   * @return hashcode
   */
  unsigned hash(unsigned key) {
    if (prefix_len == 0) return 0;

    unsigned mask = 0xFFFFFFFF << (32 - prefix_len);
    return (ntohl(key) & mask) % N_HLIST;
  }
};

struct FibTable {
  FibZone zones[33];
  int n_entries = 0;
  FibTable() {
    for (int i = 0; i < 33; ++i) {
      zones[i].prefix_len = i;
    }
  }

  void insert_node(const RoutingTableEntry& entry) {
    // select the corresponding zone and hlist
    auto& zone = zones[entry.len];
    auto& hlist = zone.hlists[zone.hash(entry.addr)];

    // check if the entry already exists
    FibNode* node_found = nullptr;
    for (auto p = hlist.first; p != nullptr; p = p->next) {
      if (entry.addr == p->entry.addr) {
        node_found = p;
        break;
      };
    }

    // if the entry already exists, then simply update it
    if (node_found != nullptr) {
      node_found->entry.nexthop = entry.nexthop;
      return;
    }
    // else
    FibNode* node = new FibNode({entry, nullptr});
    n_entries++;
    if (hlist.first == nullptr) {
      hlist.first = node;
    } else {
      hlist.last->next = node;
    }
    hlist.last = node;
  }

  void delete_node(const RoutingTableEntry& entry) {
    // select the corresponding zone and hlist
    auto& zone = zones[entry.len];
    auto& hlist = zone.hlists[zone.hash(entry.addr)];

    // if the entry does not exist
    if (hlist.first == nullptr) {
      return;
    }

    n_entries--;
    // if it is deleting the first node
    if (hlist.first->entry.addr == entry.addr) {
      auto next = hlist.first->next;
      delete hlist.first;
      hlist.first = next;
      return;
    }
    // else
    FibNode* prev = hlist.first;
    for (auto p = prev->next; p != nullptr; p = p->next) {
      if (entry.addr == p->entry.addr) {
        prev->next = p->next;
        delete p;
        return;
      }
    }
  }

  /**
   * @brief Find the node which contains the routing entry that matches the
   * given address that has the longest prefix
   * @param addr IPv4 Address
   * @return pointer to the node that contains the matching routing table entry
   */
  FibNode* prefix_match_node(unsigned addr) {
    for (int l = 32; l >= 0; --l) {
      auto& zone = zones[l];
      auto hlist_id = zone.hash(addr);
      for (auto p = zone.hlists[hlist_id].first; p != nullptr; p = p->next) {
        if (zone.prefix_len == 0) return p;

        unsigned mask = 0xFFFFFFFF << (32 - zone.prefix_len);
        auto addr_masked = ntohl(addr) & mask;
        auto entry_addr_masked = ntohl(p->entry.addr) & mask;
        if (addr_masked == entry_addr_masked) return p;
      }
    }
    return nullptr;
  }
};

FibTable routing_table;

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

unsigned query(unsigned addr) {
  FibNode *result = routing_table.prefix_match_node(addr);
  if (result != nullptr) {
    return result->entry.nexthop;
  }
  return 0;
}

评测结果