pls advise on AVL tree

Path	csiph.com!usenet.pasdenom.info!aioe.org!.POSTED!not-for-mail
From	"Mark" <mark_cruzNOTFORSPAM@hotmail.com>
Newsgroups	comp.lang.c, comp.programming
Subject	pls advise on AVL tree
Date	Thu, 29 Mar 2012 12:33:36 -0400
Organization	Aioe.org NNTP Server
Lines	75
Message-ID	<jl22st$4bv$1@speranza.aioe.org> (permalink)
NNTP-Posting-Host	QUlsvjzEAzxl4LULC7y4Eg.user.speranza.aioe.org
X-Complaints-To	abuse@aioe.org
X-MimeOLE	Produced By Microsoft MimeOLE V6.00.2900.6157
X-RFC2646	Format=Flowed; Original
X-Notice	Filtered by postfilter v. 0.8.2
X-Newsreader	Microsoft Outlook Express 6.00.2900.5931
X-Priority	3
X-MSMail-Priority	Normal
Xref	csiph.com comp.lang.c:19138 comp.programming:1388

Cross-posted to 2 groups.

Show key headers only | 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