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

Groups > comp.programming > #1388

pls advise on AVL tree

Cross-posted to 2 groups.

Show all headers | View raw

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 

Back to comp.programming | Previous | Next — Next in thread | Find similar

Thread

pls advise on AVL tree "Mark" <mark_cruzNOTFORSPAM@hotmail.com> - 2012-03-29 12:33 -0400
  Re: pls advise on AVL tree Jorgen Grahn <grahn+nntp@snipabacken.se> - 2012-03-29 23:05 +0000

csiph-web