LINUX.ORG.RU

вопрос по AVL дереву


0

1

Всем привет,

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

Спасибо !

★★

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

Очень может быть, что придется перестраивать, если новый ключ (nhkey_list) будет состоять из нескольких ключей (nhlfe_key). Критерий один: сохраняется ли упорядоченность узлов дерева по ключу (левый <= родитель <= правый). Если дерево становится вдруг неупорядоченным, то оно уже перестает быть двоичным деревом поиска.

При перестраивании можно пытаться использовать структуру старого дерева.

dave ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.