假设我有一个包含以下字段的 route_table_entry 结构:
typedef struct route_table_entry {
uint32_t prefix;
uint32_t next_hop;
uint32_t mask;
int interface;
} route_table_entry;
我想为最长前缀匹配算法构建一个 Trie,如下所示:
typedef struct trie {
route_table_entry *entry;
bool end;
struct trie *child;
struct trie *sibling;
} Trie;
好吧,我不确定这是否是存储它的最佳方式,但我应该在 Trie 中存储什么?我将如何考虑获得最大掩码?首先,我使用 routing_table 结构来执行此操作,该结构针对前缀进行排序,然后针对掩码进行递减,并使用易于找到的二进制搜索。但是使用 Trie 时,如何考虑在搜索前缀时获得具有最高掩码的前缀?