pls advise on AVL tree

Discussion in 'C Programming' started by Mark, Mar 29, 2012.

  1. Mark

    Mark Guest

    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
    Mark, Mar 29, 2012
    #1
    1. Advertising

  2. Mark

    Jorgen Grahn Guest

    On Thu, 2012-03-29, Mark wrote:
    > 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

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
    Jorgen Grahn, Mar 30, 2012
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Nobody
    Replies:
    1
    Views:
    1,459
    Dave O'Hearn
    Dec 26, 2004
  2. Nobody
    Replies:
    3
    Views:
    1,422
    Ben Pfaff
    Dec 29, 2004
  3. Zunbeltz Izaola

    avl tree

    Zunbeltz Izaola, May 30, 2005, in forum: Python
    Replies:
    5
    Views:
    755
    =?utf-8?q?Berthold_H=C3=B6llmann?=
    Jun 1, 2005
  4. John

    about AVL tree

    John, Apr 24, 2008, in forum: Java
    Replies:
    1
    Views:
    349
    Chris Smith
    Apr 24, 2008
  5. sophia

    avl tree

    sophia, Apr 22, 2008, in forum: C Programming
    Replies:
    3
    Views:
    688
    Ben Pfaff
    Apr 23, 2008
Loading...

Share This Page