C double linked list - possible memory error

[tgnelson85]

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.

#include <stdio.h>
#include <tag_c.h>
#include <stdlib.h>
#include <sys/types.h>
#include <dirent.h>
#include <sys/stat.h>
#include <string.h>
#include <unistd.h> //Only gives a warning if missing, not error.
 
#define TRUE 1
#define FALSE 0
 
//Prototypes.
char* getExtension(char *fileName); //From fileUtils.c
void init(void);
void dirSearch(char *path, char *extensionWanted);
int saveMusicCollection(void);
int loadMusicCollection(void);
void readMusicCollection(void);
 
//The original working directory, set at startup.
char *origwd = NULL;
 
//Double linked list format.
struct song {
    struct dirent *file;
    //TagLib_File *taglibFile;
    struct song *next;
    struct song *previous;
};
 
struct song *firstSong = NULL;
struct song *currentSong = NULL;
struct song *nextSong = NULL;
struct song *previousSong = NULL;
struct song *lastSong = NULL;
 
FILE *datafile = NULL;
char *filename = "music.dat";
 
 
int main(int argc, char *argv[])
{
    init();
 
    if (argc > 1) 
    {
        loadMusicCollection();
    }
    else
    {
        //Create the first song of the linked list.
        firstSong = malloc(sizeof(*firstSong));
        if (firstSong == NULL)
            printf("Error allocating memory.\n");
        currentSong = firstSong;
 
        //Search the current directory and all sub-directories for mp3 files.
        dirSearch(".", "mp3");
        //Set the next field for the last song in the linked list to NULL.
        lastSong = previousSong;
        lastSong->next = NULL;
        free(currentSong); //currentSong is also nextSong.
 
        chdir(origwd); //Now change back to the original pwd.
 
        saveMusicCollection();
        //loadMusicCollection();
    }
 
    readMusicCollection();
 
    return(0);
}
 
void init(void)
{
    origwd = (char *) malloc(PATH_MAX);
    getcwd(origwd, PATH_MAX ); //First store the pwd.
 
    //taglib_set_strings_unicode(TRUE);
}
 
/*
 * Note: after function has run the current directory will be set to
 * the last sub directory.
 */
void dirSearch(char *path, char *extensionWanted)
{
    DIR *dhandle = NULL;
    struct dirent *drecord = NULL;
    struct stat sbuf;
    int x;
    char *fileExtension = NULL;
    //TagLib_File *taglibFile = NULL;
 
    dhandle = opendir(path);
    if(dhandle == NULL)
    {
        printf("Error opening directory '%s'\n",path);
        exit(1);
    }
 
    x = chdir(path);
    if( x != 0)
    {
        printf("Error changing to '%s'\n",path);
        exit(1);
    }
 
    //printf("Directory of '%s':\n",path);
    while( (drecord = readdir(dhandle)) != NULL) //For each directory entry (dirs and files)
    {
        stat(drecord->d_name,&sbuf);
        if(S_ISDIR(sbuf.st_mode))
        {
            if( strcmp(drecord->d_name,".") == 0 ||strcmp(drecord->d_name,"..") == 0 )
            {
                //Either this dir or parent dir so we don't want to start another search here.
                continue;
            }
            dirSearch(drecord->d_name, extensionWanted); //Recursion.
        }
        else //a file
        {
            fileExtension = (char*)getExtension(drecord->d_name);
            if (fileExtension != NULL)
            {
                //Check file is of the type wanted.
                if (strcmp(fileExtension, extensionWanted) == 0)
                {
                    printf("file wanted, name = %s\n",drecord->d_name);
                    currentSong->file = drecord;
 
                    /*taglibFile = taglib_file_new(drecord->d_name);
                    if (currentSong->taglibFile == NULL)
                        printf("its null\n");
                    else
                    {
                        printf("its not null\n");
                        printf("curr song name = %s\n", currentSong->file->d_name);
                    }
                    currentSong->taglibFile = taglibFile;*/
 
                    if (previousSong == NULL) //This will be the first song.
                        currentSong->previous = NULL;
                    else
                        currentSong->previous = previousSong;
 
                    nextSong = malloc(sizeof(*nextSong));
                    if (nextSong == NULL)
                        printf("Error allocating memory.\n");
                    currentSong->next = nextSong;
 
                    previousSong = currentSong;
                    currentSong = nextSong;
                }
            }
        }
    }
    closedir(dhandle);
}
 
int saveMusicCollection(void)
{
    if (firstSong == NULL)
        return(0); //No data to write.
 
    datafile = fopen(filename, "wb");
 
    if (datafile == NULL)
    {
        printf("Error writing to %s\n", filename);
        return(1);
    }
 
    currentSong = firstSong;
    while (currentSong != NULL)
    {
        fwrite(currentSong, sizeof(*currentSong), 1, datafile);
        printf("in save File - %s\n", currentSong->file->d_name);
        currentSong = currentSong->next;
        //printf("file pointer at = %d\n", ftell(datafile));
        //printf("size of song = %d\n", sizeof(struct song));
    }
    fclose(datafile);
    printf("Data saved to %s\n", filename);
 
    return(0);
/// <summary>
////fgsg
/// </summary>
    /*datafile = fopen("test.txt", "w");
 
    if (datafile == NULL)
    {
        printf("Error writing to %s\n", filename);
        return(1);
    }
 
    currentSong = firstSong;
    while (currentSong != NULL)
    {
        fprintf(datafile, currentSong->file->d_name);
        printf("File - %s\n", currentSong->file->d_name);
        currentSong = currentSong->next;
    }
    fclose(datafile);
    printf("Data saved to %s\n", "test.txt");
 
 
    return(0);*/
}
 
int loadMusicCollection(void)
{
    datafile = fopen(filename, "rb");
    if(datafile != NULL)
    {
        firstSong = malloc(sizeof(*firstSong));
        if (firstSong == NULL)
            printf("Error allocating memory.\n");
        currentSong = firstSong;
        while(TRUE)
        {
            fread(currentSong, sizeof(*currentSong), 1, datafile);
            printf("File - %s\n", currentSong->file->d_name);
 
            if (previousSong == NULL) //This will be the first song.
                currentSong->previous = NULL;
            else
                currentSong->previous = previousSong;
 
            if (currentSong->next == NULL) //No more songs.
                break;
 
            previousSong = currentSong;
            nextSong = malloc(sizeof(*nextSong));
            if (nextSong == NULL)
                        printf("Error allocating memory.\n");
            currentSong->next = nextSong;
            currentSong = nextSong;
        }
        fclose(datafile);
        printf("Data read from %s\n", filename);
        return(0);
    }
    else
    {
        printf("Error reading from %s\n", filename);
        return(1);
    }
}
 
void readMusicCollection(void)
{
    //TagLib_Tag *tag;
 
    currentSong = firstSong;
    while (currentSong != NULL)
    {
        //if (currentSong->taglibFile != NULL)
        //{
        //    tag = taglib_file_tag(currentSong->taglibFile);
 
            printf("File - %s\n", currentSong->file->d_name);
            //printf("Artist - %s\n", taglib_tag_artist(tag));
            //printf("Title - %s\n", taglib_tag_title(tag));
        //}
        currentSong = currentSong -> next;
        puts("\n");
    }
}
 

The getExtension() funtion is in another file (no problems with this function):

#include <stdio.h>
#include <string.h>
 
/*
 *    Get the extension of a fileName (pointer to a string).
 *    Return that extension (as a pointer) or NULL if there
 *    is no extension.
 */
char* getExtension(char *fileName)
{
    char search_char = '.';
    char *position = NULL;
    int index;
    char *extension = NULL;
 
    //Search for the last ".".
    position = strrchr(fileName, search_char);
    if (position == NULL) //No extension
    {
        return(NULL);
    }
    else //Has extension.
    {
        index = fileName - position;
 
        if (index < 0)
        {
            index *= -1; //Take absolute value.
        }
 
        //Now work out the extension.
        extension = position + 1;
 
        return extension;
    }
}
 

[weaknessforcats]

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.

[tgnelson85]

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.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
struct testLL {
    int number;
    int *pnumber;
    char letter;
    char *pletter;
    struct testLL *next;
    struct testLL *previous;
};
 
char testData[5] = {'a','b','c','d','e'};
 
struct testLL *firstLL;
struct testLL *currentLL;
struct testLL *nextLL;
struct testLL *previousLL;
struct testLL *lastLL;
 
FILE *datafile = NULL;
char *filename = "ll.dat";
 
void populateLL(void);
int loadLL(void);
int saveLL(void);
void readLL(void);
void reverseReadLL(void);
 
 
 
int main(int argc, char *argv[])
{
    if (argc > 1) 
    {
        loadLL();
        readLL();
    }
    else
    {
        firstLL = malloc(sizeof(*firstLL));
        if (firstLL == NULL)
            printf("Error allocating memory.\n");
        currentLL = firstLL;
 
        populateLL();
        saveLL();
        readLL();
    }
}
 
void populateLL(void)
{
    int i;
    int *tmp;
    int tmpval;
 
    for (i=0;i<5;i++)
    {
        currentLL->number = i;
        //tmp = malloc(sizeof(i));
        //tmp = &i;
        tmpval = i;
        tmp = &tmpval;
        currentLL->pnumber = tmp;
        currentLL->letter = testData[i];
        char tmpletter = testData[i];
        currentLL->pletter = &tmpletter;
 
        printf("Populating, number = %d\n", currentLL->number);
        printf("Populating, pnumber = %d\n", *currentLL->pnumber);
        printf("Populating, letter = %c\n", currentLL->letter);
        printf("Populating, pletter = %c\n", *currentLL->pletter);
 
        if (previousLL == NULL) //first LL
            currentLL->previous = NULL;
        else
            currentLL->previous = previousLL;
 
        nextLL = malloc(sizeof(*nextLL));
        if (nextLL == NULL)
            printf("Error allocating memory.\n");
        currentLL->next = nextLL;
 
        previousLL = currentLL;
        currentLL = nextLL;
    }
 
    lastLL = previousLL;
    lastLL->next = NULL;
    free(nextLL); //currentLL is also nextLL
 
    puts("\n");
}
 
int saveLL(void)
{
    if (firstLL == NULL)
        return(0); //No data to write.
 
    datafile = fopen(filename, "wb");
 
    if (datafile == NULL)
    {
        printf("Error writing to %s\n", filename);
        return(1);
    }
 
    currentLL = firstLL;
    while (currentLL != NULL)
    {
        fwrite(currentLL, sizeof(*currentLL), 1, datafile);
        printf("Saving, number = %d\n", currentLL->number);
        printf("Saving, pnumber = %d\n", *currentLL->pnumber);
        printf("Saving, letter = %c\n", currentLL->letter);
        printf("Saving, pletter = %c\n", *currentLL->pletter);
        currentLL = currentLL->next;
    }
    fclose(datafile);
    printf("Data saved to %s\n", filename);
    puts("\n");
 
    return(0);
}
 
int loadLL(void)
{
    datafile = fopen(filename, "rb");
    if(datafile != NULL)
    {
        firstLL = malloc(sizeof(*firstLL));
        if (firstLL == NULL)
            printf("Error allocating memory.\n");
        currentLL = firstLL;
        while(1)
        {
            fread(currentLL, sizeof(*currentLL), 1, datafile);
            printf("Loading, number = %d\n", currentLL->number);
            printf("Loading, pnumber = %d\n", *currentLL->pnumber);
            printf("Loading, letter = %c\n", currentLL->letter);
            printf("Loading, pletter = %c\n", *currentLL->pletter);
 
            if (previousLL == NULL) //This will be the first LL.
                currentLL->previous = NULL;
            else
                currentLL->previous = previousLL;
 
            if (currentLL->next == NULL) //No more LLs.
                break;
 
            previousLL = currentLL;
            nextLL = malloc(sizeof(*nextLL));
            if (nextLL == NULL)
                        printf("Error allocating memory.\n");
            currentLL->next = nextLL;
            currentLL = nextLL;
        }
        fclose(datafile);
        printf("Data read from %s\n", filename);
        puts("\n");
        return(0);
    }
    else
    {
        printf("Error reading from %s\n", filename);
        puts("\n");
        return(1);
    }
}
 
void readLL(void)
{
    currentLL = firstLL;
    while (currentLL != NULL)
    {
        printf("Reading, number = %d\n", currentLL->number);
        printf("Reading, pnumber = %d\n", *currentLL->pnumber);
        printf("Reading, letter = %c\n", currentLL->letter);
        printf("Reading, pletter = %c\n", *currentLL->pletter);
        currentLL = currentLL -> next;
    }
    puts("\n");
}
 

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.

[jimwawar]

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.

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

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

[weaknessforcats]

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.

[tgnelson85]

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.

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

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

[oler1s]

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.