Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #1402

generating key for AVL tree

Cross-posted to 3 groups.

Show all headers | View raw

Hello,

I have a large system using AVL trees for fast searching of IP addresses:

struct avl_node
{
   struct avl_node *left;
   struct avl_node *right;
   ...
   void *info; /* point to nhlfe_entry describing nexthop */
}

struct nhlfe_entry
{
  u_int32_t nhlfe_ix;
  u_char opcode;
  ...
  struct nhlfe_key key;
}

/* defines a search key. */
struct nhlfe_key
{
  struct in_addr nh_addr;
  u_int32_t oif_ix;
  u_int32_t out_label;
}

So the search is based on 'struct nhlfe_key', i.e. comparator function in 
AVL tree looks like this:

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;
}

Now, what I'm trying to do is to add support for multiple next hops, that is 
I add a linked list in nhlfe_entry:

struct nhlfe_entry
{
  u_int32_t nhlfe_ix;
  u_char opcode;
  ...
  struct list *nhkey_list;
}

Each 'struct list' is struct listnode that embeds 'void *data' pointer to 
caller's private data, and this is 'struct nhlfe_key'.

So my question is -- how to generate key based on multiple elements from the 
list to store/search nodes in the tree (because otherwise now after 
introducing a list, it won't be possible to have a key based on only *one* 
next hop address). Also, they same question
applies for searching.

Also, after adding a new node in the list, do I need to re-build the tree, 
because I think this operation will change the key and as such the tree may 
become unbalanced? (or AVL tree with correct implementation naturally 
doesn't require to be rebuilt?)

Thanks!

Mark 

Back to comp.programming | Previous | Next | Find similar

Thread

generating key for AVL tree "Mark" <mark_cruzNOTFORSPAM@hotmail.com> - 2012-04-03 22:17 -0400

csiph-web