generating key for AVL tree

[Mark]

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