Generic Trees Functions Using Pointers to Function

I am trying to do some functions to manage trees that receive has argument pointers to functions.

Item is declared like this:

Code:

---

typedef void * Item;

---

There is a structure called NODE:

Code:

---

typedef struct {
  Item * item;
  struct NODE * right;
  struct NODE * left;
}NODE;

---

Until now the only successful thing i did was the declaration of the function pointer in the header file. The debug didn't show problems but I don't know if it is correct...

Code:

---

int (*less) (Item, Item);

---

Now the function that i want write:

Code:

---

void insert_node (NODE * tree, NODE * new_node, [here i want the less pointer]){

  if (less (tree->Item, new_node->Item){
    if (tree->right==NULL){
      tree->right= new_node;
      return;
    }
    else {
      insert_node(tree->right, new_node, [less function pointer again]);
    }
  }
  else{/*same thing to the other side of the tree*/}

}

---

The idea is to make generic functions to manage trees of any kind of Item (with the correct castings) and than make only functions to specify the kind of item. An example is a tree of words, and than one function like this:

Code:

---

int less_alphabetic (char * str1, char * str2){

  if (strcmp (str1, str2) <0) return 1;
  else return 0;

}

---

Try

Code:

---

void insert_node (NODE * tree, NODE * new_node, int (*less) (Item, Item) ){

  if (less (tree->Item, new_node->Item){
    if (tree->right==NULL){
      tree->right= new_node;
      return;
    }
    else {
      insert_node(tree->right, new_node, less);
    }
  }
  else{/*same thing to the other side of the tree*/}

}

---

See The Function Pointer Tutorials - Index

Also, your compare function should probably just return the result of strcmp() directly, since you need
- a before b
- a is the same as b
- a after b
to determine whether you go left, go right or stay at the current node.

It worked! Thank you =D

New problem :/ im doing now a function that balances the tree when inserting. The debugger says "Dereferencing pointer to incomplete type" because of this:

Code:

---

NODE * insert_node (NODE * tree, NODE * new_node, int (*less) (Item, Item)){

    int h1, h2, h3;

    if (tree == NULL){
        tree = new_node;
        return;
    }

    if (less(new_node->item, tree->item)){
        tree->left = insert_node(tree->left, new_node, less);
        h1 = height(tree->left->left); /*The debuger says it in this line*/
        h2 = height(tree->left->right);
        h3 = height(tree->right);/*And in this one*/
        if (h1 > h3)
            tree = rotate_right(tree);
        if (h2 > h3) {
            tree->left = rotate_left(tree->left);
            tree = rotate_right(tree);
        }
    }

---

Any idea of why?

Did you ever fix your struct declaration?

Code:

---

typedef struct NODE {
  Item * item;
  struct NODE * right;
  struct NODE * left;
}NODE;

---

If you're going to refer to "struct NODE" you have to use "struct NODE" when you declare.

Now it's working, Thanks.

How do I do a right casting of item? I did something like this

Code:

---

item = (char*) malloc (sizeof (my_string));

---

The debugger says it is an assignment form incompatible pointer type.

Than I'm using the insert_node function. I'm calling it this way:

Code:

---

insert_node (tree, new_node , strcasecmp);

---

It says i am passing argument 3 from incompatible pointer type.

item is of type Item *, so that's what you want. Also strcasecmp doesn't match the type of function you're looking for (i.e., it doesn't take two void* arguments), so you'll probably have to write a "relay" function (i.e., something that just takes the two arguments, casts them to char*, then calls strcasecmp and returns the result).

You shouldn't need to cast malloc. You probably are getting the wrong size, unless my_string just happens to be an array declared in the same scope you are using that line. And, foo( char*, char* ) is not the same as bar( void*, void * ).

edit-foiled again


Quzah.

But when the string is allocated I already do the cast of the item in that structure to char *. Or it doesn't work this way?

Quote:

---

Originally Posted by rikehmmc

But when the string is allocated I already do the cast of the item in that structure to char *. Or it doesn't work this way?

---

I'm not sure what you mean here. Your struct contains an Item*. Now, you do have to remember what type it actually is, but you have no way of changing the type of a variable.

This is in a function that creates a tree data base of words

Code:

---

NODE * create_dictionary(FILE * fp){

    char * word ;
    NODE * tree;
    NODE * aux;

    tree = create_tree();

    while (fscanf(fp, "%s", word))
    {
        aux=alloc_word_node(word);
        tree = insert_node(tree, aux, [function that compares to itens with strings]);
    }

    return tree;
}

---

Where the alloc_word_node is this funtion

Code:

---

NODE * alloc_word_node (char * word){

    NODE * node;

    node = Alloc_node();

    node->item = (char*) malloc (sizeof (word));

    return node;
}

---

Code:

---

node->item = (char*) malloc (sizeof (word));

---

So as you mentioned this line shouldn't work (I don't feel like reassembling all the pieces to try it here). But even if it does, this does not change the type of node->item. node->item is, and will always be, of type Item*.

Thanks. So i modified this line

Code:

---

    node->item = (Item*) calloc (strlen(word) +1, sizeof (char));

---

and created the function

Code:

---

int less_alphabetic (Item item1, Item item2){

    char * str1, * str2;

    str1 = (char*) item1;
    str2 = (char*) item2;

    return (strcasecmp(str1, str2));
}

---

Now everything seems ok with the debugger =)

Quote:

---

Originally Posted by rikehmmc

How do I do a right casting of item? I did something like this

Code:

---

item = (char*) malloc (sizeof (my_string));

---

---

Cprogramming.com FAQ > Casting malloc

LOL. "Those dark ages...". well, my teacher taught me to cast a malloc and a calloc, I guess he lived in that awful time where people had to open brackets, write one word, maybe a little shiny star, and only than close brackets before a malloc or a calloc =P. Anyway, thank you, it was useful

Quote:

---

Originally Posted by rikehmmc

LOL. "Those dark ages...". well, my teacher taught me to cast a malloc and a calloc, I guess he lived in that awful time where people had to open brackets, write one word, maybe a little shiny star, and only than close brackets before a malloc or a calloc =P. Anyway, thank you, it was useful

---

Casting the return of malloc and calloc is harmless ... so long as you get it right.
However C++ requires it unless you malloc() void*.

Your teacher is not wrong to suggest it... but wrong if he or she thinks it's necessary.