Thread: Adding directory/file names to a linked list

  1. #1
    Registered User
    Join Date
    Nov 2006
    Posts
    12

    Adding directory/file names to a linked list

    I'm attempting to write a program whereby it gets the name and path of all directories and files and adds them to a linked list. The list structure should hold the name/path for a directory, then any files in that directory should be held in another node off the directory node - essentially a list within a list.

    I've got the program working to the extent that it will add all the directory and file names to the one list, but it does not distinguish between the two. I've tried various things to get the filenames to add to the list within the directory list but nothing has worked for me so far.

    Anyway, if someone could show me what I need to change/add to get it working, it would be most appreciated. (By the way, I'm also pretty sure I'm not using nodetype correctly as well, but it's not so important) :-)

    Code:
    #include <dirent.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <assert.h>
    #include <sys/stat.h>
    
    enum Tnodetype {n_file, n_directory, n_symlink};
    typedef enum Tnodetype Nodetype;
    
    struct Tcell{
        struct Tcell *next;
        char * localname;
        char * fullname;
        struct Tcell * content;  // list of files in directory
        Nodetype nodetype;
    };
    typedef struct Tcell Cell, *List;
    
    char * fullname(char *root, char * name)
    {
        const char * sep = "/";
        char * res = (char *) malloc(strlen(root)+strlen(sep)+strlen(name)+1);
        strcpy(res,root);
        strcat(res,sep);
        strcat(res,name);
        return res;
    }
    
    int notdot (char * s)
    {
        return  strcmp(s,".") != 0  && strcmp(s,"..")!= 0 ;
    }
    
    int issymlink(char * name)
    {
        struct stat buf;
        lstat(name, &buf);
        return (buf.st_mode & S_IFMT) == S_IFLNK;
    }
    
    int isdir(char * name)
    {
        struct stat buf;
        lstat(name, &buf);
        return (buf.st_mode & S_IFMT) == S_IFDIR;
    }
    
    List cons(List lp, char * fname, char * lname, Nodetype nodetype)
    { 
         List res = (List)malloc(sizeof(Cell)); 
         res->localname = strdup(lname);
         res->fullname = strdup(fname);
         res->content = NULL;
         res->nodetype = nodetype;
         res->next = lp;
         return res;
    }
    
    List add_symlink(List lp, char *path, char * name)
    {
        Nodetype nodetype = n_symlink;
        return cons(lp, path, name, n_symlink);
    }
    
    List add_directory(List lp, char *path, char * name)
    {
         Nodetype nodetype = n_directory;
         return cons(lp, path, name, n_directory); 
    }
    
    List add_file(List lp, char *path, char * name)
    {
         Nodetype nodetype = n_file;
         return cons(lp, path, name, n_file);
    }
    
    List filecheck(List lp, char * dirname)
    {
        DIR *dd;
        List dir = 0;
        struct dirent *dp;
        int res = 0;
        dd = opendir(dirname);
        assert(dd);
        while ((dp = readdir(dd)))
            if (notdot(dp->d_name)){
                char * name2 = fullname(dirname, dp->d_name);
                if (issymlink(name2))  
                     lp = add_symlink(lp, name2, dp->d_name);
                else if (isdir(name2)){
                     lp = add_directory(filecheck(lp,name2), name2, dp->d_name);
                }
                else
                     lp = add_file(lp, name2, dp->d_name);
            }
        closedir(dd);
        return lp;
    }
    
    void showtree (List lp)
    {
         for ( ; lp ; lp = lp->next)
         printf("  %s - %s\n",lp->fullname);
    }
    
    int main(int argc, char * argv[]) {
        List lp = 0;
        char * dirname = strdup(( argc >1) ? argv[1] : getenv("HOME"));
        showtree(filecheck(lp, dirname));
        return (0);
    }

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Calling stat() is an expensive operation -- you should save the result.

    This function always returns 0:
    Code:
    int notdot (char * s)
    {
        return  strcmp(s,".") != 0  && strcmp(s,"..")!= 0 ;
    }
    A string can't equal "." and ".." at the same time.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    struct node
    {
        struct node *subdirectory;
        struct node *current;
        char *name;
    };
    Consider a variation of the above. Start with a node. It will be building its current directory. If the object you're checking is a file, you will add it to "current", and set its "subdirectory" to NULL (well, as well as "current" I guess). If the object you're checking is a directory, you add it to the "subdirectory" tree, and probably recursively, move to that node, repeating the process. Something like that should work. It's not the best design probably, but I'm tired and really don't care to put further thought into it at this time.


    Quzah.
    Hope is the first step on the road to disappointment.

  4. #4
    int x = *((int *) NULL); Cactus_Hugger's Avatar
    Join Date
    Jul 2003
    Location
    Banks of the River Styx
    Posts
    902
    Code:
    #include <stdio.h>
    
    int notdot (char * s)
    {
        return  strcmp(s,".") != 0  && strcmp(s,"..")!= 0 ;
    }
    
    int main()
    {
    	printf("Test of notdot() returned %d.\n", notdot("test"));
    
    	return 0;
    }
    Results in: "Test of notdot() returned 1."
    The function is correctly written. Though I might change the argument to a const char *.
    long time; /* know C? */
    Unprecedented performance: Nothing ever ran this slow before.
    Any sufficiently advanced bug is indistinguishable from a feature.
    Real Programmers confuse Halloween and Christmas, because dec 25 == oct 31.
    The best way to accelerate an IBM is at 9.8 m/s/s.
    recursion (re - cur' - zhun) n. 1. (see recursion)

  5. #5
    Registered User
    Join Date
    Nov 2006
    Posts
    12
    Quote Originally Posted by dwks
    Calling stat() is an expensive operation -- you should save the result.

    This function always returns 0:
    Code:
    int notdot (char * s)
    {
        return  strcmp(s,".") != 0  && strcmp(s,"..")!= 0 ;
    }
    A string can't equal "." and ".." at the same time.
    The sections that use stat were actually given to me like that, along with the code fragment you've highlighted. Surely that code can return something other than 0? If s = ".." then it will fail the condition (pass the first part because it does not = "." but fail the second).

    Quote Originally Posted by quzah
    Code:
    struct node
    {
        struct node *subdirectory;
        struct node *current;
        char *name;
    };
    Consider a variation of the above. Start with a node. It will be building its current directory. If the object you're checking is a file, you will add it to "current", and set its "subdirectory" to NULL (well, as well as "current" I guess). If the object you're checking is a directory, you add it to the "subdirectory" tree, and probably recursively, move to that node, repeating the process. Something like that should work. It's not the best design probably, but I'm tired and really don't care to put further thought into it at this time.


    Quzah.
    Thanks for the suggestion but I have to use the struct as given - I don't know if it is the most elegant way of implementing it but I'm stuck with it anyway.

  6. #6
    Registered User
    Join Date
    May 2006
    Posts
    903
    Surely that code can return something other than 0? If s = ".." then it will fail the condition (pass the first part because it does not = "." but fail the second).
    Then you have return 1 && 0 which evaluates to 0.

  7. #7
    Registered User
    Join Date
    Nov 2006
    Posts
    176
    cactus alrady showed its right if neither are true you have != 0 && != 0 which = 1
    Last edited by sl4nted; 12-06-2006 at 07:25 PM.

  8. #8
    Registered User
    Join Date
    Nov 2006
    Posts
    176
    Code:
    void showtree (List lp)
    {
         for ( ; lp ; lp = lp->next)
         printf("  %s - %s\n",lp->fullname);
    }
    I'm sure you see whats wrong there, unless you're meaning to add somthing later

    edit::

    also
    Code:
    char * fullname(char *root, char * name)
    {
        const char * sep = "/";
        char * res = (char *) malloc(strlen(root)+strlen(sep)+strlen(name)+1);
        strcpy(res,root);
        strcat(res,sep);
        strcat(res,name);
        return res;
    }
    test to see if the last character is already a / before you append another one
    Last edited by sl4nted; 12-06-2006 at 07:34 PM.

  9. #9
    Registered User
    Join Date
    Nov 2006
    Posts
    176
    your problem lies here
    Code:
       lp = add_file(lp, name2, dp->d_name);
    your adding the file to the main list
    which isn't what you want
    you want to add file to the main lists content list, then set the main lists content list = the new list

    lp->content = addfile(lp->content, ...

  10. #10
    Registered User
    Join Date
    Nov 2006
    Posts
    12
    Quote Originally Posted by sl4nted
    your problem lies here
    Code:
       lp = add_file(lp, name2, dp->d_name);
    your adding the file to the main list
    which isn't what you want
    you want to add file to the main lists content list, then set the main lists content list = the new list

    lp->content = addfile(lp->content, ...
    I've tried simply adding to lp->content instead of the main list, and it appears to work OK in that when I print the main list, no filenames are printed. But I keep getting a seg fault when trying to print the contents list.

    The 2 things I've tried:

    lp->content = add_file(lp, name2, dp->d_name); and
    lp->content = add_file(lp->content, name2, dp->d_name);

    both give seg faults when printing out. I can display the first two things in each list, then get the fault.

    Also, the files don't appear to be going into their corresponding directory list. Could this be because when a directory is added, it is really lp->next that is returned and so the file is getting added to the content list in the next position rather than the last?

  11. #11
    Registered User
    Join Date
    Nov 2006
    Posts
    176
    yes, you would have to process all the files first, for the way you currently have it setup. so you're probably gonna want to add a stack, so you can push directory names on it, and then process them after files have been added. you'll have to keep a tally of how many you push on, so your not processing a parents dirs in a subdir.

    lp->content = add_file(lp->content, name2, dp->d_name);
    is the way you're gonna want to go. Since as you say it does add 2 of the files. Thats good...just figure out why it doesn't add the rest.

    Also I'm not sure if you have to account for hardlinks or not. If you do, you'll want to keep the inodes you've encounted so far, and check each new inode against ones you've previously seen.

  12. #12
    Registered User
    Join Date
    Nov 2006
    Posts
    12
    Thanks for your help mate - I've actually got it adding to the content list OK now, but with the problem I mentioned about the files being added to the wrong directory. The files are added to the directory next to the one they should be added to.

  13. #13
    Registered User
    Join Date
    Nov 2006
    Posts
    176
    can you post updated code...I assume this is because you're processing files and directories at the same time still. like I said, you should use a stack and push all directory name on it, then once you've reached the end of files/directorys in that directory, start poping directorys from that stack. with this method, there is no way for the files to be added to the subdirectories content list, since the subdirectory hasn't been added yet

  14. #14
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    You're right, notdot() is correct. It just looks weird.
    The files are added to the directory next to the one they should be added to.
    Like an off-by-one-error?

    Definitely post the latest code.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list question
    By mikeman in forum C Programming
    Replies: 1
    Last Post: 11-30-2008, 01:56 PM
  2. Sorting linked list please help with CODE
    By scarlet00014 in forum C Programming
    Replies: 3
    Last Post: 09-27-2008, 11:24 PM
  3. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  4. Duplicating value of pointer to linked list
    By zephyrcat in forum C Programming
    Replies: 14
    Last Post: 01-22-2008, 03:19 PM
  5. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM