代码

#include "router.h"
#include <stdint.h>
#include <stdlib.h>
#include <fstream>

#include <vector>
using namespace std;

typedef struct {
    uint32_t addr;
    uint32_t len;
    uint32_t if_index;
    uint32_t nexthop;
} myRoutingTableEntry;

/**
* Guo Yuanbo, Tsinghua Univ., All rights reserved.
* @brief Trie tree template
* @author Guo Yuanbo
* @email guoyb17@mails.tsinghua.edu.cn
* @version 0.1
* @date 2019-11-24
* @update 2019-11-24
* @warning the tree does NOT maintain Info (see below)
*/
// Trie-Node class template
// Char: dict keyword (e.g. a-zA-Z0-9 for dictionary, 0/1 for IP address, etc.)
//     Char needs:
//     *   method int seq()   - to get sequence of this Char
//     *   static member size - to get number of kinds of Char
//     *   operator==         - to compare Char sequence
// Info: node info, may be use to store the entire word or other things (e.g. route info)
//     Info needs:
//     *   operator==         - to compare whether two Info are identical
//     *   method of copy     - to give Info to node
//         operator<<         - DEBUG only: output stream
// [WARN] The tree does NOT maintain Info!
//        Make sure Info keeps valid while tree working!
//        Also make sure memory managed properly outside the tree if necessary!
template <class Char, class Info>
class Trie {

    Info* info = nullptr; // also marks that there is a word ending up here
	Trie(const Trie&) = delete;
	Trie& operator=(const Trie& b) = delete;
	Trie* next = nullptr;

public:

	inline static const int size() { return Char::size; }

	Trie(Info* i = nullptr) {
		info = i;
		next = nullptr;
	}

	bool empty() { return info == nullptr && next == nullptr; }

	void insert(Char** word, Info* iinfo) { // word needs to end up with nullptr as a sign
		if (word[0] == nullptr) {
			if (info == nullptr) info = new Info;
			*info = *iinfo; // will overwrite previous info
			return;
		}
		if (next == nullptr) next = new Trie[size()];
		next[word[0]->seq()].insert(&word[1], iinfo);
	}

	/**
	 * @return
	 * 0 - matched and deleted
	 * 1 - this node is clear
	 * -1 - not matched due to null info
	 * -2 - NOT IN USE
	 * -3 - ERROR not matched due to no children
	 * -4 - recursively not matched
	*/
	int remove(Char** word) {
		if (word[0] == nullptr) {
			if (info != nullptr) {
				delete info;
				info = nullptr;
				if (next == nullptr) return 1;
				else return 0;
			}
			else return -1;
		}
		if (next == nullptr) return -3;
		int ans = next[word[0]->seq()].remove(&word[1]);
		if (ans == 1) {
			for (int i = 0; i < size(); i++) {
				if (!next[i].empty()) return 0;
			}
			delete[] next;
			next = nullptr;
			if (info == nullptr) return 1;
			else return 0;
		}
		else if (ans == 0) return 0;
		else return -4;
	}

	/**
	 * @param ans collect all prefix-matched info
	 *     [NOTE] ans <- vec [short ... long] match; NO guarantee for total match!
	 * @return true if this call found ans, false if not
	 */
	bool lookup_pre(Char** word, vector<const Info*>& ans) {
		if (word[0] == nullptr) {
			if (info != nullptr) {
				ans.push_back(info);
				return true;
			}
			else return false;
		}
		
		bool tflag = true;
		if (info != nullptr) ans.push_back(info);
		else tflag = false;
		if (next == nullptr) return tflag;
		return next[word[0]->seq()].lookup_pre(&word[1], ans) || tflag;
	}
};

struct Bin {
    uint8_t bin;

    static const int size = 2;

    int seq() {
        if (bin == 0) return 0;
        else if (bin == 1) return 1;
        else throw "INVALID_BIN";
    }
};

bool operator==(const Bin& a, const Bin& b) { return a.bin == b.bin; }
bool operator==(const RoutingTableEntry& a, const RoutingTableEntry& b) {
    if (a.addr != b.addr) return false;
    if (a.if_index != b.if_index) return false;
    if (a.len != b.len) return false;
    if (a.nexthop != b.nexthop) return false;
    return true;
}

void mk_word(RoutingTableEntry& info, Bin**& ans) { // ans contains both addr and len
    if (ans == nullptr) ans = new Bin*[info.len + 1];
    uint8_t ip[4];
    ip[0] = info.addr & 0xff;
    ip[1] = (info.addr & 0xff00) >> 8;
    ip[2] = (info.addr & 0xff0000) >> 16;
    ip[3] = (info.addr & 0xff000000) >> 24;
    
    for (uint32_t j = 0; j < info.len; j++) {
        ans[j] = new Bin;
        ans[j]->bin = ((ip[j / 8] & (0x1 << (7 - j % 8))) == 0) ? 0 : 1;
    }
    ans[info.len] = nullptr;
}

void mk_word(uint32_t& info, Bin**& ans) {
	if (ans == nullptr) ans = new Bin*[32 + 1];
	uint8_t ip[4];
	ip[0] = info & 0xff;
	ip[1] = (info & 0xff00) >> 8;
	ip[2] = (info & 0xff0000) >> 16;
	ip[3] = (info & 0xff000000) >> 24;

	for (uint32_t j = 0; j < 32; j++) {
		ans[j] = new Bin;
		ans[j]->bin = ((ip[j / 8] & (0x1 << (7 - j % 8))) == 0) ? 0 : 1;
	}
	ans[32] = nullptr;
}

Trie<Bin, myRoutingTableEntry> rtable(nullptr);

/**
 * @brief 插入/删除一条路由表表项
 * @param insert 如果要插入则为 true ，要删除则为 false
 * @param entry 要插入/删除的表项
 * 
 * 插入时如果已经存在一条 addr 和 len 都相同的表项，则替换掉原有的。
 * 删除时按照 addr 和 len 匹配。
 */
void update(bool insert, myRoutingTableEntry entry) {
    Bin** ans = nullptr;
    mk_word(entry, ans);
    if (insert) rtable.insert(ans, &entry);
    else rtable.remove(ans);
}

/**
 * @brief 进行一次路由表的查询，按照最长前缀匹配原则
 * @param addr 需要查询的目标地址，大端序
 * @param nexthop 如果查询到目标，把表项的 nexthop 写入
 * @param if_index 如果查询到目标，把表项的 if_index 写入
 * @return 查到则返回 true ，没查到则返回 false
 */
bool query(uint32_t addr, uint32_t *nexthop, uint32_t *if_index) {
    Bin** ans = nullptr;
    mk_word(addr, ans);
    vector<const myRoutingTableEntry*> list;
    rtable.lookup_pre(ans, list);
    if (list.empty()) return false;
    const myRoutingTableEntry value = *list[list.size() - 1];
    *nexthop = value.nexthop;
    *if_index = value.if_index;
    return true;
}

void init(int n, int q, const RoutingTableEntry *a) {
    for (int i = 0; i < n; i++) {
        myRoutingTableEntry tmp;
        tmp.addr = a[i].addr;
        tmp.len = a[i].len;
        tmp.if_index = 0;
        tmp.nexthop = a[i].nexthop;
        Bin** ans;
        mk_word(tmp, ans);
        rtable.insert(ans, &tmp);
    }
}

unsigned query(unsigned addr) {
	uint32_t* nexthop = nullptr;
    uint32_t* if_index = nullptr;
    if (!query(addr, nexthop, if_index)) return 0;
    else return *nexthop;
}

评测结果