pls advise on AVL tree

[Mark]

Hello

I have a big piece of software I'm modifying now to add additional feature,
the big chunk is data structures and related API. Initially I had:

struct nhlfe_entry
{
u_int32_t nhlfe_ix;
u_int32_t xc_ix;
...
u_char nkey [1];
};

Now it's going to be (so nkey will be eliminated) :

struct nhlfe_entry
{
u_int32_t nhlfe_ix;
u_int32_t xc_ix;
..
struct list nkey_list; /* list -- is linked list library */
};

Every node of the linked list will contain object of type:

struct nhlfe_key
{
..
union
{
struct nhlfe_key_ipv4 ipv4;
struct nhlfe_key_ipv6 ipv6;
u_char val;
} u;
};

struct nhlfe_key_ipv4
{
struct pal_in4_addr nh_addr;
u_int32_t oif_ix;
u_int32_t out_label;
};

Now, objects of type 'struct nhlfe_entry' are added in AVL tree and
comparison function is quite straightforward -- based on nkey, something
like this:

int compare_fn(void *data1, void *data2)
{
int ret;
struct nhlfe_entry *nh1, *nh2;
struct nhlfe_key *key1, *key2;
...
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->u.ipv4.nh_addr, &key2->u.ipv4.nh_addr, sizeof(struct
pal_in4_addr));
...
}

But now I'm having a list of 'nhlfe_key ' and I'm thinking how the
comparison function to be modifed -- the simple idea that pops up is to
compare key of a new element to be added in the tree with the last key in
the list. Does it make sense or it may impact the correctness of the tree
behavior (specifically balance) ?

Would be very hankful for advices !

Mark

 

[Jorgen Grahn]

Hello

I have a big piece of software I'm modifying now to add additional feature,
the big chunk is data structures and related API. Initially I had:

struct nhlfe_entry
{
u_int32_t nhlfe_ix;
u_int32_t xc_ix;
...
u_char nkey [1];
};

Now it's going to be (so nkey will be eliminated) :

struct nhlfe_entry
{
u_int32_t nhlfe_ix;
u_int32_t xc_ix;
..
struct list nkey_list; /* list -- is linked list library */
};

Every node of the linked list will contain object of type:

struct nhlfe_key
{
..
union
{
struct nhlfe_key_ipv4 ipv4;
struct nhlfe_key_ipv6 ipv6;
u_char val;
} u;
};

struct nhlfe_key_ipv4
{
struct pal_in4_addr nh_addr;
u_int32_t oif_ix;
u_int32_t out_label;
};

Now, objects of type 'struct nhlfe_entry' are added in AVL tree and
comparison function is quite straightforward -- based on nkey, something
like this:

int compare_fn(void *data1, void *data2)
{ ....
ret = memcmp(&key1->u.ipv4.nh_addr, &key2->u.ipv4.nh_addr, sizeof(struct
pal_in4_addr));
...
}

This is already a problem. Do you really want memcmp() to order your
tree? Remember that in C there may be padding between the fields of
struct nhlfe_key, and this padding may be any random garbage data, and
will affect your memcmp() result.

But now I'm having a list of 'nhlfe_key ' and I'm thinking how the
comparison function to be modifed -- the simple idea that pops up is to
compare key of a new element to be added in the tree with the last key in
the list. Does it make sense or it may impact the correctness of the tree
behavior (specifically balance) ?

One thing you often do is "lexicographical comparison" -- the kind
that strcmp() does. If you can compare two struct Foo, you can apply
that to compare two arrays/lists/sequences of struct Foo. In
strcmp()'s case, "struct Foo" is simply char.

/Jorgen