[romez777 0]

Приветствую,

 

имеется большая написанная давно на С система 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-ов, нужно ли перестраивать дерево, ведь вероятно ключ поменяется, что произойдет с деревом?

 

Спасибо.

[xvr 12]

И вот теперь возникает вопрос -- по какому ключу хранить/искать элементы в дерево?

По всему списку nhkey_list. Бежать по элементам списка и сравнивать попарно. Как только вернет нечто, отличное от 0. то это и возвращать. Если один из списков исчерпался раньше другого - возвращать -1/1

При добавлении нового элемента в список nexthop-ов, нужно ли перестраивать дерево, ведь вероятно ключ поменяется, что произойдет с деревом?

Ключ менять нельзя. Придется элемент удалить из дерева, добавить в него (в элемент) nexthop и вставить снова в дерево.

 

Тут настоятельно напрашивается сделать ключ по чему нибудь не столь обширному и изменчивому :rolleyes:

 

Либо сделать так, что бы каждый отдельный nhlfe_key был представлен отдельным элементом в дереве, а ваш конечный nhlfe_entry собирать вне дерева

[romez777 0]

По всему списку nhkey_list. Бежать по элементам списка и сравнивать попарно. Как только вернет нечто, отличное от 0. то это и возвращать. Если один из списков исчерпался раньше другого - возвращать -1/1

Ключ менять нельзя. Придется элемент удалить из дерева, добавить в него (в элемент) nexthop и вставить снова в дерево.

 

Тут настоятельно напрашивается сделать ключ по чему нибудь не столь обширному и изменчивому :rolleyes:

 

Либо сделать так, что бы каждый отдельный nhlfe_key был представлен отдельным элементом в дереве, а ваш конечный nhlfe_entry собирать вне дерева

 

Спасибо за ответ. А что скажете насчет следующего -- в качестве ключа _всегда_ использовать самый первый элемент списка, тот что в голове списка, сравнивать/добавлять по нему. Но возможна ситуация когда одинаковый nexthop присутствует в нескольких узлах дерева (например, один nexthop для группы IP сетей).

 

Либо делать хеш, crc на каждый из лист-нодов, суммировать и это будет ключом. Из минусов -- каждый раз при добавлении нового nexthop'а пересчитывать ключ, удалять нод из дерева и добавлять с новым ключом.

 

Comments are welcome :)

[xvr 12]

Если основное назначение AVL дерева - 'быстро искать по IP', то в качестве ключей в нем и должны выступать IP. Т.к. у вас в узлах дерева предполагается хранить несколько IP, то само это дерево в AVL структуру с ключами по IP просто не ляжет.

Еще раз рекомендую - делайте 2 разных контейнера: AVL с IP в качестве ключей и 2й контейнер, можно простой массив с nhlfe_entry. Элементы из AVL дерева должны ссылаться на наборы элементов из 2го контейнера.