Всем привет,
Собственно имеется большая написанная давно на С система IP маршрутизации. Один из ее элементов — быстрый поиск IP адресов, для этого активно пользуются AVL деревья.
struct avl_node
{
struct avl_node *left;
struct avl_node *right;
...
void *info; /* содержит указатель на структуру описывающую IP адрес etc. */
}
Далее, в дереве хранятся структуры описывающие следующий в маршруте узел (nexthop) - адрес узла, выходной интерфейс и т.д. Вот так сделано сейчас :
struct nhlfe_entry
{
u_int32_t nhlfe_ix;
u_char opcode;
...
struct nhlfe_key key;
}
struct nhlfe_key
{
struct in_addr nh_addr;
u_int32_t oif_ix;
u_int32_t out_label;
}
Поиск по этому дереву делается по ключу типа 'struct nhlfe_key', т.е. в avl дереве ф-ция компаратор выглядит примерно так:
static int
mpls_cmp_nhlfe_ipv4_key (void *data1, void* data2)
{
struct nhlfe_entry *nh1, *nh2;
struct nhlfe_key *key1, *key2;
int ret;
nh1 = (struct nhlfe_entry *) data1;
nh2 = (struct nhlfe_entry *) data2;
key1 = (struct nhlfe_key *) nh1->nkey;
key2 = (struct nhlfe_key *) nh2->nkey;
ret = memcmp (&key1->nh_addr, &key2->nh_addr, sizeof (struct in_addr));
if (ret != 0)
return ret;
if (key1->oif_ix > key2->oif_ix)
return 1;
else if (key1->oif_ix < key2->oif_ix)
return -1;
if (key1->out_label > key2->out_label)
return 1;
else if (key1->out_label < key2->out_label)
return -1;
return 0;
}
Т.е. ключ как бы составной и критерий сравнения лексикографический -- все элементы должны совпасть.
Теперь — в struct nhlfe_entry добавляется поддержка многих next-hop'ов, т.е. будет список из struct nhlfe_key:
struct nhlfe_entry
{
u_int32_t nhlfe_ix;
u_char opcode;
...
struct list *nhkey_list;
}
Каждый элемент 'struct list' это struct listnode который имеет 'void *data' на собственно данные, и это будет struct nhlfe_key.
И вот теперь возникает вопрос — по какому ключу хранить/искать элементы в дерево? При добавлении нового элемента в список nexthop-ов, нужно ли перестраивать дерево, ведь вероятно ключ поменяется, что произойдет с деревом?
Спасибо !
