Tr ie для наибольшего совпадения префиксов - PullRequest
Новая
       87

Tr ie для наибольшего совпадения префиксов

0 голосов
/ 01 апреля 2020

Предположим, у меня есть структура route_table_entry со следующими полями: 

typedef struct route_table_entry {
    uint32_t prefix;
    uint32_t next_hop;
    uint32_t mask;
    int interface;
} route_table_entry;

И я хочу построить Tr ie для алгоритма сопоставления самого длинного префикса, например: 

typedef struct trie {
    route_table_entry *entry;
    bool end;
    struct trie *child;
    struct trie *sibling;
} Trie;

Ну, я не уверен, что это действительно лучший способ хранить это, но что мне хранить в Tr ie? Как бы я учел, что получу максимальную маску? Сначала я сделал это с помощью структуры routing_table, которая была отсортирована по префиксу, а затем уменьшена по маске, и с помощью двоичного поиска, который было бы легко найти. Но с Tr ie как учесть, что я получаю префикс с самой высокой маской при поиске префикса?

...