Thread: Link List Insert prob

  1. #1
    Registered User
    Join Date
    Dec 2008
    Posts
    4

    Link List Insert prob

    I'm trying to create a list where each element is a structure containing file attributes. I seem to have the the list construction ok but my Insert function is not working. All compiles but I get a segmentation fault and I cant see why. Here's my code:

    Code:
    #include <dirent.h>
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <assert.h>
    #include <sys/stat.h>
    #include <time.h>
    
    typedef struct TPayload *Payload;
    struct TPayload {
      int ftype;  //type i.e. file or Dir
      const char * fname;  //name of file
      const char * fpath; //path of file relative to root
      int fsize; //size of file in bytes
      time_t modtime; //time lat modified
    };
    
    typedef struct TCell *List;
    struct TCell {
      struct TCell * next;
      Payload data;
    };
    
    //Initalises 1 element of the list
    Payload initial(int filetype, const char * filename, const char * filepath, int filesize, time_t modifytime)
    {
      Payload p = (Payload)malloc(sizeof(struct TPayload));
      p->ftype = filetype; 
      p->fname = filename;
      p->fpath = filepath;
      p->fsize = filesize;
      p->modtime = modifytime;
      printf("Payload intialsed successfully! \n");
      return p;
    }
    
    //Construct the list
    List cons(Payload p, List lp)
    {
      List res = (List) malloc(sizeof(struct TCell));
      assert(res);
      res->next = lp;
      res->data = (Payload)malloc(sizeof(struct TPayload));
      assert(res->data);
      res->data->ftype = p->ftype;
      assert(res->data->ftype);
      res->data->fname = strdup(p->fname);
      assert(res->data->fname);
      res->data->fpath = strdup(p->fpath);
      assert(res->data->fpath);
      res->data->fsize = p->fsize;
      assert(res->data->fsize);
      res->data->modtime = p->modtime;
      assert(res->data->modtime);
      printf("list constructed ok\n");
      return res;
    }
    
    void show(List lp)
    {
      char timestr[100];
      
      for (; lp; lp = lp->next){
        printf ("Type of file =  %d\n",lp->data->ftype);
        printf("Filename =  %s\n",lp->data->fname);
        printf("Path of file =  %s\n",lp->data->fpath);
        printf("Size of file =  %d Bytes\n",lp->data->fsize);
        strftime(timestr, 100, "%d-%m-%Y %H:%M:%S",localtime(&lp->data->modtime));
        printf("Last modified on  %s\n",timestr);
      }
    }
    
    /***********Believe my problem is in insert function here *******/
    /****************************************************************/
    List insert( Payload p, List lp)
    {
      if ( lp == 0) return cons(p,lp);
      if (strlen(p->fname) < strlen(lp->data->fname)) 
          return cons(p, lp);
      return cons(lp->data, insert(p, lp->next));
    }
    
    
    int main()
    {
      //Body of main not important only for testing functions
      Payload p1 = initial(1,"file1","path1",10,10);
      Payload p2 = initial(0,"file2","path2",20,20);
      Payload p3 = initial(1,"file3","path3",30,30);
      Payload p4 = initial(0,"file4","path4",40,40);
      Payload p5 = initial(1,"file5","path5",50,50);
      
      List lis1 =  cons(p1,lis1);
      show(lis1);
      printf("test before insert\n");
      lis1=insert(p1,lis1);
      lis1=insert(p2,lis1);
      lis1=insert(p3,lis1);
      lis1=insert(p4,lis1);
      lis1=insert(p5,lis1);
      printf("test before show");
      show(lis1);
      return 0;
    }
    Any help be much appreciated.

  2. #2
    Registered User
    Join Date
    Apr 2008
    Posts
    396
    I guess you're using linux, if you get a segmentation fault, use gdb to run your program (remember to compile with -g to keep the symbols), it will spot the exact location of the problem.

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Your insert function seems to be the biggest memory leak we've had in a while. Is there a reason for using a lisp-like cons function here? I don't see any reason to make insert recursive, when you could just walk the list until you find where the element should go and insert it there, rather than recreate the preceding parts of the list from scratch every time.

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Like tabstop says, you are probably just simply running out of memory when inserting.

    I also find it curious that you are inserting the files in length order - what's idea behind that?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User
    Join Date
    Dec 2008
    Posts
    4
    No idea really I've started the insert function again from scratch.

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Actually, I take that back:
    Code:
    List lis1 =  cons(p1,lis1);
    What value does lis1 have here?

    I also needed to comment out this line:
    Code:
      //  assert(res->data->ftype);
    since ftype is actualy zero in some of your sample data.

    It also seems like your list is not quite right.
    Code:
    test before showType of file =  1
    Filename =  file5
    Path of file =  path5
    Size of file =  50 Bytes
    Last modified on  01-01-1970 00:00:50
    It's only showing the LAST entry in the list. It may be that I messed up insert, but I don't think so.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    Registered User
    Join Date
    Dec 2008
    Posts
    4
    not sure anymore I have got mind in a twist now.

    Your first question I think lis1 should contain only the first payload element I created there.

    Code:
    void insert(List head, Payload p){
    List ptr2=head;
    if(ptr2==NULL){
    ptr2=(List)malloc(sizeof(struct TCell));
    ptr2->data->ftype=p->ftype;  //Seg Fault here
    ptr2->data->fname=p->fname;
    ptr2->data->fpath=p->fpath;
    ptr2->data->fsize=p->fsize;
    ptr2->data->modtime=p->modtime;
    ptr2->next=NULL;
    }else{
    while(ptr2 != NULL){
    ptr2 = ptr2->next;
    }
    ptr2=(List)malloc(sizeof(struct TCell));
    ptr2->data->ftype=p->ftype;
    ptr2->data->fname=p->fname;
    ptr2->data->fpath=p->fpath;
    ptr2->data->fsize=p->fsize;
    ptr2->data->modtime=p->modtime;
    ptr2->next=NULL;
    }
    }
    Wrote this new insert function but still get seg fault. This time in insert at line marked above.
    Last edited by Bebs; 12-03-2008 at 10:15 PM. Reason: add code

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Because you are not allocating the Data?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    Registered User
    Join Date
    Dec 2008
    Posts
    4
    Ye that was why.
    Allocated space for data now and no seg fault. good times.
    now show function displays nothing. bad times.
    Last edited by Bebs; 12-03-2008 at 10:29 PM. Reason: typo

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. urgent help please...
    By peter_hii in forum C++ Programming
    Replies: 11
    Last Post: 10-30-2006, 06:37 AM
  2. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 AM
  3. Replies: 6
    Last Post: 03-02-2005, 02:45 AM
  4. Undefined Structure in Link List
    By _Cl0wn_ in forum C Programming
    Replies: 1
    Last Post: 03-22-2003, 05:57 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM