Thread: Generic Trees Functions Using Pointers to Function

  1. #1
    Registered User
    Join Date
    May 2011
    Posts
    19

    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;
    
    }

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    May 2011
    Posts
    19
    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?
    Last edited by rikehmmc; 05-14-2011 at 02:31 PM. Reason: new problem

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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.

  5. #5
    Registered User
    Join Date
    May 2011
    Posts
    19
    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.

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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).

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  8. #8
    Registered User
    Join Date
    May 2011
    Posts
    19
    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?

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by rikehmmc View Post
    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.

  10. #10
    Registered User
    Join Date
    May 2011
    Posts
    19
    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;
    }

  11. #11
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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*.

  12. #12
    Registered User
    Join Date
    May 2011
    Posts
    19
    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 =)

  13. #13
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    Quote Originally Posted by rikehmmc View Post

    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

  14. #14
    Registered User
    Join Date
    May 2011
    Posts
    19
    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

  15. #15
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by rikehmmc View Post
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Storing function pointers in generic pointers
    By Boxknife in forum C Programming
    Replies: 6
    Last Post: 08-01-2009, 01:33 PM
  2. Generic Pointers to structures
    By dunxton in forum C Programming
    Replies: 8
    Last Post: 02-20-2009, 10:23 AM
  3. Replies: 4
    Last Post: 11-23-2003, 07:15 AM
  4. Function Pointers to Templated Functions
    By Speedy5 in forum C++ Programming
    Replies: 6
    Last Post: 02-12-2003, 08:11 AM
  5. function pointers and member functions
    By thor in forum C++ Programming
    Replies: 5
    Last Post: 03-19-2002, 04:22 PM