By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,341 Members | 1,376 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,341 IT Pros & Developers. It's quick & easy.

C double linked list - possible memory error

P: 6
Hello, C question here (running on Linux, though there should be no platform specific code).

After reading through a few examples, and following one in a book, for linked lists i thought i would try my own small program. The problem is, I seem to be having trouble with memory, i.e. sometimes my program will work and display the correct output, and sometimes it will not and display garbage (in a printf call) so i assume i have been using memory not allocated to my linked list structure.

My code is below and you can ignore anything refering to taglib (it gets id3 tags in mp3 files) as i have commented it out. The loadMusicCollection() function is also unused in this example as i am having problems before that.

Basically, everything works if (from main()) i call dirSearch then readMusicCollection(), i.e. the output makes sense. However, as in the example below, when i call saveMusicCollection() the output goes funny (i get File - s���������� rather than File - song1.mp3 or whatever) so i assume it is accessing an incorrect memory location. However, as far as i am aware, i have correctly used malloc() and free() and i cannot work out why calling saveMusicCollection() before readMusicCollection() would cause the output to corrupt.

If anyone wants to run this - it searches in the current directory and all sub dirs for files of type mp3 (can be changed) and at the moment will print out the file name (stored in the double linked list) - don't bother running it with any command line arguments as it will just call loadMusicCollection(). I ran it with 2 mp3 files in the current directory, 1 in a sub dir and 2 in a sub dir of that.

Any help appreciated.

Tony.

Expand|Select|Wrap|Line Numbers
  1. #include <stdio.h>
  2. #include <tag_c.h>
  3. #include <stdlib.h>
  4. #include <sys/types.h>
  5. #include <dirent.h>
  6. #include <sys/stat.h>
  7. #include <string.h>
  8. #include <unistd.h> //Only gives a warning if missing, not error.
  9.  
  10. #define TRUE 1
  11. #define FALSE 0
  12.  
  13. //Prototypes.
  14. char* getExtension(char *fileName); //From fileUtils.c
  15. void init(void);
  16. void dirSearch(char *path, char *extensionWanted);
  17. int saveMusicCollection(void);
  18. int loadMusicCollection(void);
  19. void readMusicCollection(void);
  20.  
  21. //The original working directory, set at startup.
  22. char *origwd = NULL;
  23.  
  24. //Double linked list format.
  25. struct song {
  26.     struct dirent *file;
  27.     //TagLib_File *taglibFile;
  28.     struct song *next;
  29.     struct song *previous;
  30. };
  31.  
  32. struct song *firstSong = NULL;
  33. struct song *currentSong = NULL;
  34. struct song *nextSong = NULL;
  35. struct song *previousSong = NULL;
  36. struct song *lastSong = NULL;
  37.  
  38. FILE *datafile = NULL;
  39. char *filename = "music.dat";
  40.  
  41.  
  42. int main(int argc, char *argv[])
  43. {
  44.     init();
  45.  
  46.     if (argc > 1) 
  47.     {
  48.         loadMusicCollection();
  49.     }
  50.     else
  51.     {
  52.         //Create the first song of the linked list.
  53.         firstSong = malloc(sizeof(*firstSong));
  54.         if (firstSong == NULL)
  55.             printf("Error allocating memory.\n");
  56.         currentSong = firstSong;
  57.  
  58.         //Search the current directory and all sub-directories for mp3 files.
  59.         dirSearch(".", "mp3");
  60.         //Set the next field for the last song in the linked list to NULL.
  61.         lastSong = previousSong;
  62.         lastSong->next = NULL;
  63.         free(currentSong); //currentSong is also nextSong.
  64.  
  65.         chdir(origwd); //Now change back to the original pwd.
  66.  
  67.         saveMusicCollection();
  68.         //loadMusicCollection();
  69.     }
  70.  
  71.     readMusicCollection();
  72.  
  73.     return(0);
  74. }
  75.  
  76. void init(void)
  77. {
  78.     origwd = (char *) malloc(PATH_MAX);
  79.     getcwd(origwd, PATH_MAX ); //First store the pwd.
  80.  
  81.     //taglib_set_strings_unicode(TRUE);
  82. }
  83.  
  84. /*
  85.  * Note: after function has run the current directory will be set to
  86.  * the last sub directory.
  87.  */
  88. void dirSearch(char *path, char *extensionWanted)
  89. {
  90.     DIR *dhandle = NULL;
  91.     struct dirent *drecord = NULL;
  92.     struct stat sbuf;
  93.     int x;
  94.     char *fileExtension = NULL;
  95.     //TagLib_File *taglibFile = NULL;
  96.  
  97.     dhandle = opendir(path);
  98.     if(dhandle == NULL)
  99.     {
  100.         printf("Error opening directory '%s'\n",path);
  101.         exit(1);
  102.     }
  103.  
  104.     x = chdir(path);
  105.     if( x != 0)
  106.     {
  107.         printf("Error changing to '%s'\n",path);
  108.         exit(1);
  109.     }
  110.  
  111.     //printf("Directory of '%s':\n",path);
  112.     while( (drecord = readdir(dhandle)) != NULL) //For each directory entry (dirs and files)
  113.     {
  114.         stat(drecord->d_name,&sbuf);
  115.         if(S_ISDIR(sbuf.st_mode))
  116.         {
  117.             if( strcmp(drecord->d_name,".") == 0 ||strcmp(drecord->d_name,"..") == 0 )
  118.             {
  119.                 //Either this dir or parent dir so we don't want to start another search here.
  120.                 continue;
  121.             }
  122.             dirSearch(drecord->d_name, extensionWanted); //Recursion.
  123.         }
  124.         else //a file
  125.         {
  126.             fileExtension = (char*)getExtension(drecord->d_name);
  127.             if (fileExtension != NULL)
  128.             {
  129.                 //Check file is of the type wanted.
  130.                 if (strcmp(fileExtension, extensionWanted) == 0)
  131.                 {
  132.                     printf("file wanted, name = %s\n",drecord->d_name);
  133.                     currentSong->file = drecord;
  134.  
  135.                     /*taglibFile = taglib_file_new(drecord->d_name);
  136.                     if (currentSong->taglibFile == NULL)
  137.                         printf("its null\n");
  138.                     else
  139.                     {
  140.                         printf("its not null\n");
  141.                         printf("curr song name = %s\n", currentSong->file->d_name);
  142.                     }
  143.                     currentSong->taglibFile = taglibFile;*/
  144.  
  145.                     if (previousSong == NULL) //This will be the first song.
  146.                         currentSong->previous = NULL;
  147.                     else
  148.                         currentSong->previous = previousSong;
  149.  
  150.                     nextSong = malloc(sizeof(*nextSong));
  151.                     if (nextSong == NULL)
  152.                         printf("Error allocating memory.\n");
  153.                     currentSong->next = nextSong;
  154.  
  155.                     previousSong = currentSong;
  156.                     currentSong = nextSong;
  157.                 }
  158.             }
  159.         }
  160.     }
  161.     closedir(dhandle);
  162. }
  163.  
  164. int saveMusicCollection(void)
  165. {
  166.     if (firstSong == NULL)
  167.         return(0); //No data to write.
  168.  
  169.     datafile = fopen(filename, "wb");
  170.  
  171.     if (datafile == NULL)
  172.     {
  173.         printf("Error writing to %s\n", filename);
  174.         return(1);
  175.     }
  176.  
  177.     currentSong = firstSong;
  178.     while (currentSong != NULL)
  179.     {
  180.         fwrite(currentSong, sizeof(*currentSong), 1, datafile);
  181.         printf("in save File - %s\n", currentSong->file->d_name);
  182.         currentSong = currentSong->next;
  183.         //printf("file pointer at = %d\n", ftell(datafile));
  184.         //printf("size of song = %d\n", sizeof(struct song));
  185.     }
  186.     fclose(datafile);
  187.     printf("Data saved to %s\n", filename);
  188.  
  189.     return(0);
  190. /// <summary>
  191. ////fgsg
  192. /// </summary>
  193.     /*datafile = fopen("test.txt", "w");
  194.  
  195.     if (datafile == NULL)
  196.     {
  197.         printf("Error writing to %s\n", filename);
  198.         return(1);
  199.     }
  200.  
  201.     currentSong = firstSong;
  202.     while (currentSong != NULL)
  203.     {
  204.         fprintf(datafile, currentSong->file->d_name);
  205.         printf("File - %s\n", currentSong->file->d_name);
  206.         currentSong = currentSong->next;
  207.     }
  208.     fclose(datafile);
  209.     printf("Data saved to %s\n", "test.txt");
  210.  
  211.  
  212.     return(0);*/
  213. }
  214.  
  215. int loadMusicCollection(void)
  216. {
  217.     datafile = fopen(filename, "rb");
  218.     if(datafile != NULL)
  219.     {
  220.         firstSong = malloc(sizeof(*firstSong));
  221.         if (firstSong == NULL)
  222.             printf("Error allocating memory.\n");
  223.         currentSong = firstSong;
  224.         while(TRUE)
  225.         {
  226.             fread(currentSong, sizeof(*currentSong), 1, datafile);
  227.             printf("File - %s\n", currentSong->file->d_name);
  228.  
  229.             if (previousSong == NULL) //This will be the first song.
  230.                 currentSong->previous = NULL;
  231.             else
  232.                 currentSong->previous = previousSong;
  233.  
  234.             if (currentSong->next == NULL) //No more songs.
  235.                 break;
  236.  
  237.             previousSong = currentSong;
  238.             nextSong = malloc(sizeof(*nextSong));
  239.             if (nextSong == NULL)
  240.                         printf("Error allocating memory.\n");
  241.             currentSong->next = nextSong;
  242.             currentSong = nextSong;
  243.         }
  244.         fclose(datafile);
  245.         printf("Data read from %s\n", filename);
  246.         return(0);
  247.     }
  248.     else
  249.     {
  250.         printf("Error reading from %s\n", filename);
  251.         return(1);
  252.     }
  253. }
  254.  
  255. void readMusicCollection(void)
  256. {
  257.     //TagLib_Tag *tag;
  258.  
  259.     currentSong = firstSong;
  260.     while (currentSong != NULL)
  261.     {
  262.         //if (currentSong->taglibFile != NULL)
  263.         //{
  264.         //    tag = taglib_file_tag(currentSong->taglibFile);
  265.  
  266.             printf("File - %s\n", currentSong->file->d_name);
  267.             //printf("Artist - %s\n", taglib_tag_artist(tag));
  268.             //printf("Title - %s\n", taglib_tag_title(tag));
  269.         //}
  270.         currentSong = currentSong -> next;
  271.         puts("\n");
  272.     }
  273. }
  274.  
The getExtension() funtion is in another file (no problems with this function):

Expand|Select|Wrap|Line Numbers
  1. #include <stdio.h>
  2. #include <string.h>
  3.  
  4. /*
  5.  *    Get the extension of a fileName (pointer to a string).
  6.  *    Return that extension (as a pointer) or NULL if there
  7.  *    is no extension.
  8.  */
  9. char* getExtension(char *fileName)
  10. {
  11.     char search_char = '.';
  12.     char *position = NULL;
  13.     int index;
  14.     char *extension = NULL;
  15.  
  16.     //Search for the last ".".
  17.     position = strrchr(fileName, search_char);
  18.     if (position == NULL) //No extension
  19.     {
  20.         return(NULL);
  21.     }
  22.     else //Has extension.
  23.     {
  24.         index = fileName - position;
  25.  
  26.         if (index < 0)
  27.         {
  28.             index *= -1; //Take absolute value.
  29.         }
  30.  
  31.         //Now work out the extension.
  32.         extension = position + 1;
  33.  
  34.         return extension;
  35.     }
  36. }
  37.  
Dec 13 '07 #1
Share this Question
Share on Google+
6 Replies


weaknessforcats
Expert Mod 5K+
P: 9,197
fwrite(currentSong, sizeof(*currentSong), 1, datafile);
This code writes the sizeof a struct song. A struct song contains three pointers so I expect you are writing 12 bytes that are really three pointers.

I don't see you actually writing the name of the song. You can't justy write a struct song, if for no opther reason than two of the members are linked list pointers.

The same is true with your malloc's. I see you allocate a sizeof(*currentsong), which is allocating a struct song, or 12 bytes. I don't see where you actually allocate memory for the name of the song.
Dec 13 '07 #2

P: 6
This code writes the sizeof a struct song. A struct song contains three pointers so I expect you are writing 12 bytes that are really three pointers.

I don't see you actually writing the name of the song. You can't justy write a struct song, if for no opther reason than two of the members are linked list pointers.

The same is true with your malloc's. I see you allocate a sizeof(*currentsong), which is allocating a struct song, or 12 bytes. I don't see where you actually allocate memory for the name of the song.
So for each field in the struct (the file name and the pointers) i have to malloc it?

I was under the impression that the filename (dirent) had been malloc'ed by the function that i called to get it (drecord = readdir(dhandle)) and that this memory allocation stayed until i free()'ed it...



I created a smaller more manageable test file to try and understand the situation better.

Expand|Select|Wrap|Line Numbers
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. struct testLL {
  6.     int number;
  7.     int *pnumber;
  8.     char letter;
  9.     char *pletter;
  10.     struct testLL *next;
  11.     struct testLL *previous;
  12. };
  13.  
  14. char testData[5] = {'a','b','c','d','e'};
  15.  
  16. struct testLL *firstLL;
  17. struct testLL *currentLL;
  18. struct testLL *nextLL;
  19. struct testLL *previousLL;
  20. struct testLL *lastLL;
  21.  
  22. FILE *datafile = NULL;
  23. char *filename = "ll.dat";
  24.  
  25. void populateLL(void);
  26. int loadLL(void);
  27. int saveLL(void);
  28. void readLL(void);
  29. void reverseReadLL(void);
  30.  
  31.  
  32.  
  33. int main(int argc, char *argv[])
  34. {
  35.     if (argc > 1) 
  36.     {
  37.         loadLL();
  38.         readLL();
  39.     }
  40.     else
  41.     {
  42.         firstLL = malloc(sizeof(*firstLL));
  43.         if (firstLL == NULL)
  44.             printf("Error allocating memory.\n");
  45.         currentLL = firstLL;
  46.  
  47.         populateLL();
  48.         saveLL();
  49.         readLL();
  50.     }
  51. }
  52.  
  53. void populateLL(void)
  54. {
  55.     int i;
  56.     int *tmp;
  57.     int tmpval;
  58.  
  59.     for (i=0;i<5;i++)
  60.     {
  61.         currentLL->number = i;
  62.         //tmp = malloc(sizeof(i));
  63.         //tmp = &i;
  64.         tmpval = i;
  65.         tmp = &tmpval;
  66.         currentLL->pnumber = tmp;
  67.         currentLL->letter = testData[i];
  68.         char tmpletter = testData[i];
  69.         currentLL->pletter = &tmpletter;
  70.  
  71.         printf("Populating, number = %d\n", currentLL->number);
  72.         printf("Populating, pnumber = %d\n", *currentLL->pnumber);
  73.         printf("Populating, letter = %c\n", currentLL->letter);
  74.         printf("Populating, pletter = %c\n", *currentLL->pletter);
  75.  
  76.         if (previousLL == NULL) //first LL
  77.             currentLL->previous = NULL;
  78.         else
  79.             currentLL->previous = previousLL;
  80.  
  81.         nextLL = malloc(sizeof(*nextLL));
  82.         if (nextLL == NULL)
  83.             printf("Error allocating memory.\n");
  84.         currentLL->next = nextLL;
  85.  
  86.         previousLL = currentLL;
  87.         currentLL = nextLL;
  88.     }
  89.  
  90.     lastLL = previousLL;
  91.     lastLL->next = NULL;
  92.     free(nextLL); //currentLL is also nextLL
  93.  
  94.     puts("\n");
  95. }
  96.  
  97. int saveLL(void)
  98. {
  99.     if (firstLL == NULL)
  100.         return(0); //No data to write.
  101.  
  102.     datafile = fopen(filename, "wb");
  103.  
  104.     if (datafile == NULL)
  105.     {
  106.         printf("Error writing to %s\n", filename);
  107.         return(1);
  108.     }
  109.  
  110.     currentLL = firstLL;
  111.     while (currentLL != NULL)
  112.     {
  113.         fwrite(currentLL, sizeof(*currentLL), 1, datafile);
  114.         printf("Saving, number = %d\n", currentLL->number);
  115.         printf("Saving, pnumber = %d\n", *currentLL->pnumber);
  116.         printf("Saving, letter = %c\n", currentLL->letter);
  117.         printf("Saving, pletter = %c\n", *currentLL->pletter);
  118.         currentLL = currentLL->next;
  119.     }
  120.     fclose(datafile);
  121.     printf("Data saved to %s\n", filename);
  122.     puts("\n");
  123.  
  124.     return(0);
  125. }
  126.  
  127. int loadLL(void)
  128. {
  129.     datafile = fopen(filename, "rb");
  130.     if(datafile != NULL)
  131.     {
  132.         firstLL = malloc(sizeof(*firstLL));
  133.         if (firstLL == NULL)
  134.             printf("Error allocating memory.\n");
  135.         currentLL = firstLL;
  136.         while(1)
  137.         {
  138.             fread(currentLL, sizeof(*currentLL), 1, datafile);
  139.             printf("Loading, number = %d\n", currentLL->number);
  140.             printf("Loading, pnumber = %d\n", *currentLL->pnumber);
  141.             printf("Loading, letter = %c\n", currentLL->letter);
  142.             printf("Loading, pletter = %c\n", *currentLL->pletter);
  143.  
  144.             if (previousLL == NULL) //This will be the first LL.
  145.                 currentLL->previous = NULL;
  146.             else
  147.                 currentLL->previous = previousLL;
  148.  
  149.             if (currentLL->next == NULL) //No more LLs.
  150.                 break;
  151.  
  152.             previousLL = currentLL;
  153.             nextLL = malloc(sizeof(*nextLL));
  154.             if (nextLL == NULL)
  155.                         printf("Error allocating memory.\n");
  156.             currentLL->next = nextLL;
  157.             currentLL = nextLL;
  158.         }
  159.         fclose(datafile);
  160.         printf("Data read from %s\n", filename);
  161.         puts("\n");
  162.         return(0);
  163.     }
  164.     else
  165.     {
  166.         printf("Error reading from %s\n", filename);
  167.         puts("\n");
  168.         return(1);
  169.     }
  170. }
  171.  
  172. void readLL(void)
  173. {
  174.     currentLL = firstLL;
  175.     while (currentLL != NULL)
  176.     {
  177.         printf("Reading, number = %d\n", currentLL->number);
  178.         printf("Reading, pnumber = %d\n", *currentLL->pnumber);
  179.         printf("Reading, letter = %c\n", currentLL->letter);
  180.         printf("Reading, pletter = %c\n", *currentLL->pletter);
  181.         currentLL = currentLL -> next;
  182.     }
  183.     puts("\n");
  184. }
  185.  
If run with no arguments (so the linked list is populated, saved to disk, then read) i get:

Populating, number = 0
Populating, pnumber = 0
Populating, letter = a
Populating, pletter = a
Populating, number = 1
Populating, pnumber = 1
Populating, letter = b
Populating, pletter = b
Populating, number = 2
Populating, pnumber = 2
Populating, letter = c
Populating, pletter = c
Populating, number = 3
Populating, pnumber = 3
Populating, letter = d
Populating, pletter = d
Populating, number = 4
Populating, pnumber = 4
Populating, letter = e
Populating, pletter = e


Saving, number = 0
Saving, pnumber = 1
Saving, letter = a
Saving, pletter = e
Saving, number = 1
Saving, pnumber = 1
Saving, letter = b
Saving, pletter = e
Saving, number = 2
Saving, pnumber = 1
Saving, letter = c
Saving, pletter = e
Saving, number = 3
Saving, pnumber = 1
Saving, letter = d
Saving, pletter = e
Saving, number = 4
Saving, pnumber = 1
Saving, letter = e
Saving, pletter = e
Data saved to ll.dat


Reading, number = 0
Reading, pnumber = -1073973416
Reading, letter = a
Reading, pletter =
Reading, number = 1
Reading, pnumber = -1073973416
Reading, letter = b
Reading, pletter =
Reading, number = 2
Reading, pnumber = -1073973416
Reading, letter = c
Reading, pletter =
Reading, number = 3
Reading, pnumber = -1073973416
Reading, letter = d
Reading, pletter =
Reading, number = 4
Reading, pnumber = -1073973416
Reading, letter = e
Reading, pletter =




I think the problem i'm having is with pointers within the structures, i'm not sure if i'm allocating them correctly (at the start of populateLL()). Any ideas?

Tony.
Dec 13 '07 #3

P: 15
Expand|Select|Wrap|Line Numbers
  1. firstLL = malloc(sizeof(*firstLL));
When you use malloc, calloc, realloc what is returned is a void pointer. You need to make a cast to the pointer type you want to use.
Expand|Select|Wrap|Line Numbers
  1. tmp = (int*)malloc(sizeof(int));
I am a little surprised you didn't get either a warning or error for this. So your code becomes
Expand|Select|Wrap|Line Numbers
  1. firstLL = (testLL*)malloc(sizeof(*firstLL));
There are a few places you need to change this.

You do need to malloc inside your structs'. You will need to malloc next, previous etc for each struct.

Hope this helps
Dec 13 '07 #4

weaknessforcats
Expert Mod 5K+
P: 9,197
So for each field in the struct (the file name and the pointers) i have to malloc it?
Yes. If you don't malloc each member all you have is a pointer and no memory that it points at.

I was under the impression that the filename (dirent) had been malloc'ed by the function that i called to get it (drecord = readdir(dhandle)) and that this memory allocation stayed until i free()'ed it...
If so, then this takes care of allocating the members.

However your write is:
fwrite(currentLL, sizeof(*currentLL), 1, datafile);
which writes the sizeof(*currentLL). *currentLL is a pointer to a struct testLL. That struct contains 5 pointers and 1 int. Probably, that is 24 bytes. SO I expect you are writing 24 bytes.

What you are supposed to write is the length of the name of the song. That means you need to find the length of the name of the song, malloc() that much memory, then copy the song name to that allocation, then write that allocation to disc, then delete the allocation.
Dec 13 '07 #5

P: 6
When you use malloc, calloc, realloc what is returned is a void pointer. You need to make a cast to the pointer type you want to use.
Expand|Select|Wrap|Line Numbers
  1. tmp = (int*)malloc(sizeof(int));
I am a little surprised you didn't get either a warning or error for this. So your code becomes
Expand|Select|Wrap|Line Numbers
  1. firstLL = (testLL*)malloc(sizeof(*firstLL));
There are a few places you need to change this.

You do need to malloc inside your structs'. You will need to malloc next, previous etc for each struct.

Hope this helps
I was under the impression that this was bad practice to cast the return pointer from malloc as this can hide errors/warnings, see for example:

http://everything2.com/index.pl?node_id=590986
Dec 14 '07 #6

Expert 100+
P: 671
It is bad practice to cast malloc. I know books don't necessarily indicate so, but practically speaking, casting malloc is a bad idea.

It gets you nothing positive. It'll compile fine with or without a cast. This isn't C++. C will auto convert void pointers to the appropriate type.

But there are negatives:

- Extra maintenance. You now have to maintain the type mentioned in the cast. The canonical recommended form is type *p = malloc(n * sizeof(*p)). Notice how I don't mention the type in the call to malloc.
- If you don't include stdlib.h, the compiler will not warn about the missing include. Thing logically about how C assumes int return type by default, and how this might be a disaster at runtime and to debug.

Also see http://c-faq.com/malloc/mallocnocast.html.
Dec 14 '07 #7

Post your reply

Sign in to post your reply or Sign up for a free account.