代码

#include "router.h"
#include <cstdint>
#include <netinet/in.h>
#include <cstdlib>


typedef struct TrieNode {
    TrieNode *children[2] = {NULL, NULL};
    uint32_t addr = 0;
    uint32_t nexthop = 0;
    bool is_entry = false;
} TrieNode;

TrieNode root;

void initialize_TrieNode(TrieNode *node, uint32_t addr, uint32_t nexthop,
                         TrieNode *chlid0, TrieNode *child1, bool is_entry) {
    node->addr = addr;
    node->nexthop = nexthop;
    node->is_entry = is_entry;
    node->children[0] = chlid0;
    node->children[1] = child1;
}

/**
 * @brief 插入/删除一条路由表表项
 * @param insert 如果要插入则为 true ，要删除则为 false
 * @param entry 要插入/删除的表项
 *
 * 插入时如果已经存在一条 addr 和 len 都相同的表项，则替换掉原有的。
 * 删除时按照 addr 和 len **精确** 匹配。
 */
void update(bool insert, RoutingTableEntry entry) {
    uint32_t addr = ntohl(entry.addr);
    uint32_t len = entry.len;
    uint32_t nexthop = entry.nexthop;

    TrieNode *prev_node = NULL;
    TrieNode *curr_node = &root;

    uint32_t mask = 0x80000000;

    if (insert) {
        for (int i = 0; i < len; ++i) {
            int8_t entry_bit = (addr & mask) >> (31 - i);
            prev_node = curr_node;
            curr_node = curr_node->children[entry_bit];
            if (curr_node == NULL) {
                curr_node = (TrieNode *) malloc(sizeof(TrieNode));
                initialize_TrieNode(curr_node, 0, 0, NULL, NULL, false);
                prev_node->children[entry_bit] = curr_node;
            }
            mask >>= 1;
        }
        curr_node->addr = addr;
        curr_node->is_entry = true;
        curr_node->nexthop = nexthop;
    } else {
        for (int i = 0; i < len; ++i) {
            int8_t entry_bit = (addr & mask) >> (31 - i);
            prev_node = curr_node;
            curr_node = curr_node->children[entry_bit];
            if (curr_node == NULL) {
                return;
            }
            mask >>= 1;
        }
        if (curr_node->addr == addr) {
            curr_node->is_entry = false;
        }
    }
}

/**
 * @brief 进行一次路由表的查询，按照最长前缀匹配原则
 * @param addr 需要查询的目标地址，网络字节序
 * @param nexthop 如果查询到目标，把表项的 nexthop 写入
 * @return 查到则返回 true ，没查到则返回 false
 */
bool prefix_query(uint32_t addr, uint32_t *nexthop) {
    addr = ntohl(addr);

    bool found = false;
    uint32_t nexthop_tmp;
    TrieNode *curr_node = &root;
    uint32_t mask = 0x80000000;
    for (int i = 0; i < 32; ++i) {
        int8_t entry_bit = (addr & mask) >> (31 - i);
        curr_node = curr_node->children[entry_bit];
        if (curr_node == NULL) {
            break;
        }
        if (curr_node->is_entry) {
            found = true;
            nexthop_tmp = curr_node->nexthop;
        }
        mask >>= 1;
    }
    if (found) {
        *nexthop = nexthop_tmp;
        return true;
    }
    return false;
}

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

unsigned query(unsigned addr) {
        unsigned nexthop;
        bool res = prefix_query(addr, &nexthop);
	return res && nexthop;
}

评测结果