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 .
|
Similar Threads
