Thread: C Tree Help

  1. #1
    Registered User
    Join Date
    Oct 2012
    Posts
    1

    C Tree Help

    I'm trying to simulate a tree with d number of depths and n number of nodes. I call the function create_tree and pass arguments of the root folder, the maximum depth and nodes. So if I call root 2 3, I expected as follows
    root/0
    root/1
    root/2
    root/0/0
    root/0/1
    ...
    root/2/2

    However, my code repeats
    root/0
    root/1
    root/2
    root/0
    root/1
    root/2

    I'm suspecting that my array of struct d's isn't working as expected. Can anyone help me understand the cause of this?

    Thank you.


    Code is posted below
    Code:
     
    struct d {
      char *path;           //path to node
      char *name;          //path + current node  = name    
      struct dir *up;       //to parent
    };
    
    void create_tree(struct d **p,char *name,int depth, int children) {
            struct dir *cur_head, *tp;
            cur_head=malloc(sizeof(struct dir));
            tp=malloc(sizeof(struct dir));
            cur_head->up=*p;
            cur_head->name=(char *)name;
            cur_head->path=(char *)name;
            tp=cur_head;
            struct dir open[1];
            open[0]=*tp;                                            //set up for first root dir   
            int open_size = sizeof(open)/sizeof(struct dir);       
            int i;
            for(i=0; i<depth; i++){
                    double breadth_as_double = pow(children,i+1);          //size of array c^d       
                    int breadth_size = (int)breadth_as_double;    
                    struct dir array_dir[breadth_size];
                    int pos_in_array = 0;
                    int pos_in_open;
                    for(pos_in_open=0; pos_in_open<open_size; pos_in_open++){
                            struct dir *cur_parent;
                            cur_parent=malloc(sizeof(struct dir));
                            cur_parent=&open[pos_in_open];
                            printf("current_parent: %s\n", cur_parent->name);
                            int j;
                            for(j=0; j<children; j++){
                                    struct dir *breadth_p;
                                    breadth_p=malloc(sizeof(struct dir));
                                    char buffer[8];
                                    char name_buff[1024];
                                    snprintf(buffer,sizeof(buffer), "/%d", j);
                                    breadth_p->up=cur_parent;
                                    breadth_p->path=breadth_p->up->name;
                                    snprintf(name_buff,sizeof(name_buff), "%s%s",breadth_p->path,buffer); 
                                    printf("name of dir: %s\n", name_buff);          //remove later
                                    breadth_p->name=name_buff;
                                    array_dir[pos_in_array]=*breadth_p;
                                    pos_in_array++;
                            }
                    }
                    open_size = breadth_size;
                    struct dir open[breadth_size];           //does this initalize a new array?
                    int x;
                    for(x=0;x<breadth_size;x++){
                            struct dir *temp;
                            temp=malloc(sizeof(struct dir));
                            temp=&array_dir[x];
                            open[x]=*temp;
                            printf("loop test: %s\n", temp->name);
                    }
            }
    }
    Last edited by thenotsowin; 10-22-2012 at 07:01 PM.

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    This was from a fairly brief review of your code. There's probably more, but this should keep you plenty busy for a while:

    • It would help if you provided enough code for us to compile and run this.
    • Do you compile with warnings turned all the way up? Did you resolve all the issues there? If not, do so, or provide the error messages with corresponding line numbers.
    • Have you run this through a debugger and/or something like valgrind to check for common memory usage problems.
    • What is a 'struct dir'? You don't have the definition. Is it the same as a 'struct d'? If so, that's an easy way to accidentally declare or malloc something of the wrong size/type.
    • There is a better idiom for malloc'ing a struct. This would be very helpful if struct d and struct dir are different, and you used the wrong type somewhere. See below:
    • You redeclare the identifier 'open' in two different scopes (lines 15 and 47). Is this intentional? It's confusing at best, and at worse, totally wrong. Furthermore, at least on a *nix system, open is the name of a system function for IO. You might want to pick a better name.
    • Declaring an array of 1 element (like you do on line 15) is almost always wrong. Just declare a single variable.
    • I find putting a space character on either side of your operators often makes code easier to read, and thus makes mistakes easier to find and fix.
    • There's no need for a type cast, you can just do cur_head->name = name; and similar for path.


    The malloc idiom:
    Code:
    struct dir *tp;
    tp = malloc(sizeof(*tp));
    This way, whatever type tp is supposed to be, you always malloc the right amount of space for it. If you have to change the type later, you only change the declaration, the malloc statement will always work. It works because tp is of type "pointer to struct dir", so *tp dereferences the pointer, and is of type "struct dir", thus you malloc the right amount of space.

    I suspect the root of your problem is lines 28 and 52. You malloc space for a variable, and store that result in a pointer, then assign the address of an element from a local array into that pointer. That has two major problems:

    1. You have a memory leak. You lose the address returned by malloc when you do the assignment on the following line, so you can't ever free it.
    2. The malloc'ed memory will exist after the function is done, but the local arrays will disappear, thus any pointer to any elements in those arrays is invalid. This results in undefined behavior. It will probably just give garbage output, but could cause your program to crash, or do anything it wants (the behavior is undefined).


    The solution you want is probably to use memcpy to copy the contents instead of just the pointer values. Alternatively, you may be able to malloc the memory earlier in your function, and read/assign directly into the malloc'ed struct, instead of into array_dir or open, and reassign/recopy again later.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Rooted Tree (Family tree)
    By ch4 in forum C Programming
    Replies: 4
    Last Post: 10-14-2008, 04:24 PM
  2. Replies: 2
    Last Post: 08-01-2007, 01:08 PM
  3. display tree data in binary tree format
    By xddxogm3 in forum C++ Programming
    Replies: 4
    Last Post: 12-11-2003, 12:47 AM
  4. Replies: 5
    Last Post: 05-23-2003, 01:11 PM
  5. b-tree (not binary tree) implementation help
    By Unregistered in forum C++ Programming
    Replies: 8
    Last Post: 01-02-2002, 03:30 PM

Tags for this Thread