Reading and writing a linked list from a file

  • (3 Pages)
  • +
  • 1
  • 2
  • 3

43 Replies - 5611 Views - Last Post: 05 August 2012 - 03:10 AM Rate Topic: -----

#1 giwrg98  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 26-July 12

Reading and writing a linked list from a file

Posted 26 July 2012 - 08:40 AM

I have written this piece of code: http://ideone.com/zPzvy and for some reason, after I have backed up and loaded from the file, the linked list appears empty. What have I done wrong?
Is This A Good Question/Topic? 0
  • +

Replies To: Reading and writing a linked list from a file

#2 jimblumberg  Icon User is offline

  • member icon


Reputation: 4066
  • View blog
  • Posts: 12,548
  • Joined: 25-December 09

Re: Reading and writing a linked list from a file

Posted 26 July 2012 - 08:46 AM

First please post your code in your post, in code tags.

:code:


int List::backup()    {
    FILE *fp;
 
    if( (fp = fopen(FILE_NAME, "wb") ) == NULL )
        return 1;
 
    int i;
    Node *dummy;
 
    fwrite(&members, sizeof(members), 1, fp);
    for(i = 0, dummy = list; i < members; i++, dummy = dummy->next)
        fwrite(dummy, sizeof(Node), 1, fp);
 
    fclose(fp);
    return 0;
}
 
int List::load()   {
    FILE *fp;
 
    if( (fp = fopen(FILE_NAME, "rb")) == NULL )
        return 1;
 
    int i;
    Node *dummy;
 
    fread(&members, sizeof(members), 1, fp);
    list = dummy;
 
    for(i = 0; i < members; i++, dummy = dummy->next)   {
        dummy = new Node;
        fread(dummy, sizeof(Node), 1, fp);
    }
 
    return 0;
}
 

Next you will need to show more code. With the code you posted it looks like you are only using local variables that will be destroyed when the function ends. Also you have a fairly large memory leak. You use new on the same pointer multiple times without freeing the memory between news.

Jim

This post has been edited by jimblumberg: 26 July 2012 - 08:47 AM

Was This Post Helpful? 0
  • +
  • -

#3 giwrg98  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 26-July 12

Re: Reading and writing a linked list from a file

Posted 26 July 2012 - 09:05 AM

main.cpp
#include <cstdio>
#include <cstdlib>
#include <string.h>
#include "node.h"
#include "list.h"

using namespace std;

#define DEBUG

int main()
{
    Node test, next_test;
    List list;

#ifdef BACKUP
    test.i = 21;
    test.d = 12.12398;
    strcpy(test.s, "Bla Bla Bla");

    next_test.i = 82;
    next_test.d = 3.333333333;
    strcpy(next_test.s, "Bourou Bourou");

    list.add(&test);
    list.add(&next_test);
    list.printcon();
    list.backup();
    printf("Backup was succesfull!\n");
#endif


#ifdef  LOAD
    list.load();
    list.printcon();
#endif
    return 0;
}


list.cpp
#include "list.h"

#define FILE_NAME       "file.dat"

List::List()
{
    list = NULL;
    members = 0;
}

int List::printcon() {
    int i;
    Node *dummy;

    if(list == NULL)
        return -1;

    for(i = 0, dummy = list; i < members; i++, dummy = dummy->next)
        printf("%d %lf %s\n", dummy->i, dummy->d, dummy->s);

    return (i + 1);
}

int List::add(Node *n)  {
    if(list == NULL)    {
        list = n;
        members++;
        return 0;
    }

    Node *dummy;
    int i;

    for(dummy = list, i = 0; i < members - 1; dummy = dummy->next, i++)
        ;

    dummy->next = n;
    members++;
    //dummy->next->next = NULL;

    return 0;
}

int List::backup()    {
    FILE *fp;

    if( (fp = fopen(FILE_NAME, "wb") ) == NULL )
        return 1;

    int i;
    Node *dummy;

    fwrite(&members, sizeof(members), 1, fp);
    for(i = 0, dummy = list; i < members; i++, dummy = dummy->next)
        fwrite(dummy, sizeof(Node), 1, fp);

    fclose(fp);
    return 0;
}

int List::load()   {
    FILE *fp;

    if( (fp = fopen(FILE_NAME, "rb")) == NULL )
        return 1;

    int i;
    Node *dummy;

    fread(&members, sizeof(members), 1, fp);
    list = dummy;

    for(i = 0; i < members; i++, dummy = dummy->next)   {
        dummy = new Node;
        fread(dummy, sizeof(Node), 1, fp);
    }

    return 0;
}


node.cpp
#include <cstdio>
#include <cstdlib>
#include "node.h"

Node::Node()
{
}

void Node::printcon(void) {
    printf("%d %lf %s\n", i, d, s);
}


list.h
#ifndef LIST_H
#define LIST_H

#include <cstdio>
#include <cstdlib>
#include <string.h>
#include "node.h"


class List
{
public:
    List();
    int printcon();
    int add(Node *n);
    int members;
    int backup();
    int load();

private:
    Node *list;
};

#endif // LIST_H


node.h
#ifndef NODE_H
#define NODE_H

class Node
{
    public:
        Node();
        void printcon(void);
        int i;
        char s[120];
        double d;
        Node *next;
};

#endif // NODE_H


Where exactly is the memory leak?
Was This Post Helpful? 0
  • +
  • -

#4 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3569
  • View blog
  • Posts: 11,089
  • Joined: 05-May 12

Re: Reading and writing a linked list from a file

Posted 26 July 2012 - 09:34 AM

On line 74 of list.cpp, you use new to allocate space for the nodes in the list. No problem there, except later, when the list is destroyed, you never go through the list deallocate the nodes. Massive leak.

The other massive leak is if you call List::add() one or more times, and then call List::load(), on line 71 of list.cpp, you just change the pointer to the head of the list without freeing your old nodes.

But you have other issues:
  • In main.cpp lines 25-26, you are passing pointers to memory that is in the stack. If you implement a destructor to deallocate the nodes, you'll be trying to deallocate memory that was never new'd.

  • In list.cpp line 73, you are using dummy->next which you just read off disk. Unless you control exactly the memory address to where objects are created (eg. implement your own new operator), pointers are useless when read from storage because you have no guarantees of what block of memory you'll next time around.

This post has been edited by Skydiver: 26 July 2012 - 09:37 AM

Was This Post Helpful? 0
  • +
  • -

#5 giwrg98  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 26-July 12

Re: Reading and writing a linked list from a file

Posted 26 July 2012 - 11:18 AM

View PostSkydiver, on 26 July 2012 - 09:34 AM, said:

On line 74 of list.cpp, you use new to allocate space for the nodes in the list. No problem there, except later, when the list is destroyed, you never go through the list deallocate the nodes. Massive leak.

The other massive leak is if you call List::add() one or more times, and then call List::load(), on line 71 of list.cpp, you just change the pointer to the head of the list without freeing your old nodes.

But you have other issues:
  • In main.cpp lines 25-26, you are passing pointers to memory that is in the stack. If you implement a destructor to deallocate the nodes, you'll be trying to deallocate memory that was never new'd.

  • In list.cpp line 73, you are using dummy->next which you just read off disk. Unless you control exactly the memory address to where objects are created (eg. implement your own new operator), pointers are useless when read from storage because you have no guarantees of what block of memory you'll next time around.

So if we put aside the memory leaks, the main problem is that I should dynamically alocate with Load::add()?
Was This Post Helpful? 0
  • +
  • -

#6 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3569
  • View blog
  • Posts: 11,089
  • Joined: 05-May 12

Re: Reading and writing a linked list from a file

Posted 26 July 2012 - 11:23 AM

Yes. Either the caller allocates, or the list allocates. Different people have different philosophies on it. With your current function signature, it looks like caller allocates.
Was This Post Helpful? 0
  • +
  • -

#7 giwrg98  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 26-July 12

Re: Reading and writing a linked list from a file

Posted 27 July 2012 - 06:53 AM

View PostSkydiver, on 26 July 2012 - 11:23 AM, said:

Yes. Either the caller allocates, or the list allocates. Different people have different philosophies on it. With your current function signature, it looks like caller allocates.

I changed main.cpp:
#include <cstdio>
#include <cstdlib>
#include <string.h>
#include "node.h"
#include "list.h"

using namespace std;

#define LOAD

int main()
{
    List list;

#ifdef BACKUP
    list.add(12, 8.234, "Bla Bla");
    list.add(6, 3.33333, "Bourou Bourou");

    list.printcon();
    list.backup();
    printf("Backup was succesfull!\n");
#endif


#ifdef  LOAD
    list.load();
    printf("List was loaded.\n");
    list.printcon();
#endif
    return 0;
}



and list.cpp to:
#include "list.h"

#define FILE_NAME       "file.dat"

List::List()
{
    list = NULL;
    members = 0;
}

int List::printcon() {
    int i;
    Node *dummy;

    if(list == NULL)
        return -1;

    for(i = 0, dummy = list; i < members; i++, dummy = dummy->next)
        printf("%d %lf %s\n", dummy->i, dummy->d, dummy->s);

    return (i + 1);
}

int List::add(int i, double d, char *s)  {
    if(list == NULL)    {
        list = new Node;
        list->i = i;
        list->d = d;
        strcpy(list->s, s);
        members++;
        return 0;
    }

    Node *dummy;
    int counter;

    for(dummy = list, counter = 0; counter < members - 1; dummy = dummy->next, counter++)
        ;

    dummy->next = new Node;
    dummy->next->i = i;
    dummy->next->d = d;
    strcpy(dummy->next->s, s);
    members++;

    return 0;
}

int List::backup()    {
    FILE *fp;

    if( (fp = fopen(FILE_NAME, "wb") ) == NULL )
        return 1;

    int i;
    Node *dummy;

    fwrite(&members, sizeof(members), 1, fp);
    for(i = 0, dummy = list; i < members; i++, dummy = dummy->next)
        fwrite(dummy, sizeof(Node), 1, fp);

    fclose(fp);
    return 0;
}

int List::load()   {
    FILE *fp;

    if( (fp = fopen(FILE_NAME, "rb")) == NULL )
        return 1;

    int i;
    Node *dummy;

    fread(&members, sizeof(members), 1, fp);
    list = dummy;

    for(i = 0; i < members; i++, dummy = dummy->next)   {
        dummy = new Node;
        fread(dummy, sizeof(Node), 1, fp);
    }

    return 0;
}


Was This Post Helpful? 0
  • +
  • -

#8 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3569
  • View blog
  • Posts: 11,089
  • Joined: 05-May 12

Re: Reading and writing a linked list from a file

Posted 27 July 2012 - 12:32 PM

Good job changing the add().

You are still leaking memory because you don't have a destructor for the list which deletes the nodes in the list.

Looking at your load code, you still have some issues:
Line 76 set list to point to wherever dummy is pointing. But dummy is uninitialized at line 73.
Line 78 still uses dummy->next, but remember what I said that pointers are not valid after retrieving them from storage (unless you write your own new operator).

The minimally invasive way to load your list is to have a local Node instance. fread() into that instance, and then call your add() method to add those values that you read in.

This post has been edited by Skydiver: 27 July 2012 - 12:33 PM

Was This Post Helpful? 0
  • +
  • -

#9 giwrg98  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 26-July 12

Re: Reading and writing a linked list from a file

Posted 28 July 2012 - 01:13 AM

View PostSkydiver, on 27 July 2012 - 12:32 PM, said:

Pointers are not valid after retrieving them from storage (unless you write your own new operator).

What do you mean by that?
Was This Post Helpful? 0
  • +
  • -

#10 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3569
  • View blog
  • Posts: 11,089
  • Joined: 05-May 12

Re: Reading and writing a linked list from a file

Posted 28 July 2012 - 01:35 AM

When you call new, memory is allocated, and the address of that memory is returned to you.
int main()
{
    int *x = new int;
    std::cout << x;
    return 0;
}



You have no guarantees that the next time you run your program, you'll get the same memory address.

So in your code, you have you class Node:
class Node
{
    public:
        Node();
        void printcon(void);
        int i;
        char s[120];
        double d;
        Node *next;
};


which you write out to a file. This includes the address of the next Node. In your current code for load(), you just read the entire Node from the file and assume that pointer to the next node is still good.
Was This Post Helpful? 0
  • +
  • -

#11 giwrg98  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 26-July 12

Re: Reading and writing a linked list from a file

Posted 28 July 2012 - 01:41 AM

I changed list.cpp a bit, but it still doesn't work:
#include "list.h"
 
#define FILE_NAME       "file.dat"
 
List::List()
{
    list = NULL;
    members = 0;
}
 
int List::printcon() {
    int i;
    Node *dummy;
 
    if(list == NULL)
        return -1;
 
    for(i = 0, dummy = list; i < members; i++, dummy = dummy->next)
        printf("%d %lf %s\n", dummy->i, dummy->d, dummy->s);
 
    return (i + 1);
}
 
int List::add(int i, double d, char *s)  {
    if(list == NULL)    {
        list = new Node;
        list->i = i;
        list->d = d;
        strcpy(list->s, s);
        members++;
        return 0;
    }
 
    Node *dummy;
    int counter;
 
    for(dummy = list, counter = 0; counter < members - 1; dummy = dummy->next, counter++)
        ;
 
    dummy->next = new Node;
    dummy->next->i = i;
    dummy->next->d = d;
    strcpy(dummy->next->s, s);
    members++;
 
    return 0;
}
 
int List::backup()    {
    FILE *fp;
 
    if( (fp = fopen(FILE_NAME, "wb") ) == NULL )
        return 1;
 
    int i;
    Node *dummy;
 
    fwrite(&members, sizeof(members), 1, fp);
    for(i = 0, dummy = list; i < members; i++, dummy = dummy->next)
        fwrite(dummy, sizeof(Node), 1, fp);
 
    fclose(fp);
    return 0;
}
 
int List::load()   {
    FILE *fp;
 
    if( (fp = fopen(FILE_NAME, "rb")) == NULL )
        return 1;
    
    Node new_node;
    int tmp;

    fread(&tmp, sizeof(tmp), 1, fp);
    
    for(int i = 0; i < tmp; i++)	{
	fread(&new_node, sizeof(Node), 1, fp);
	this->add(new_node.i, new_node.d, new_node.s);
    }
	
    /*
    int i;
    Node *dummy;
 
    fread(&members, sizeof(members), 1, fp);
    
    dummy = new Node;
    fread(dummy, sizeof(Node), 1, fp);
    list = dummy;
    
    for(i = 1, dummy = dummy->next; i < members; i++, dummy = dummy->next)   {
        dummy = new Node;
        fread(dummy, sizeof(Node), 1, fp);
    }
    */
    return 0;
}



So, would that fix the problem:
int List::load()   {
    FILE *fp;
 
    if( (fp = fopen(FILE_NAME, "rb")) == NULL )
        return 1;
    
    /*
    Node new_node;
    int tmp;

    fread(&tmp, sizeof(tmp), 1, fp);
    
    for(int i = 0; i < tmp; i++)	{
	fread(&new_node, sizeof(Node), 1, fp);
	this->add(new_node.i, new_node.d, new_node.s);
    }
	
    */
    int i;
    Node *dummy;
 
    fread(&members, sizeof(members), 1, fp);
    
    dummy = new Node;
    fread(dummy, sizeof(Node), 1, fp);
    list = dummy;
    
    
    for(i = 1, dummy = dummy->next; i < members; i++, dummy = dummy->next)   {
        dummy = new Node;
        fread(dummy, sizeof(Node), 1, fp);
	dummy->next = new Node;
    }

    return 0;
}


Was This Post Helpful? 0
  • +
  • -

#12 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3569
  • View blog
  • Posts: 11,089
  • Joined: 05-May 12

Re: Reading and writing a linked list from a file

Posted 28 July 2012 - 01:58 AM

View Postgiwrg98, on 28 July 2012 - 01:41 AM, said:

I changed list.cpp a bit, but it still doesn't work:
Spoiler


You have to be a lot more descriptive beyond "it still doesn't work". What behavior were you seeing? What were you expecting to happen? What steps did you take to try to narrow down the problem?

View Postgiwrg98, on 28 July 2012 - 01:41 AM, said:

So, would that fix the problem:
Spoiler


This fixes your old problem where you were accessing memory that was not allocated. Unfortunately you have a new problem where you are not reading data into the new Node that you allocated on line 32. Instead you are allocating yet another Node on line 30 and reading data into that Node.
Was This Post Helpful? 0
  • +
  • -

#13 giwrg98  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 26-July 12

Re: Reading and writing a linked list from a file

Posted 28 July 2012 - 02:30 AM

To test it I run the code in main after I had defined the BACKUP macro:
#include <cstdio>
#include <cstdlib>
#include <string.h>
#include "node.h"
#include "list.h"

using namespace std;

#define LOAD

int main()
{
    List list;

#ifdef BACKUP
    list.add(12, 8.234, "Bla Bla");
    list.add(6, 3.33333, "Bourou Bourou");

    list.printcon();
    list.backup();
    printf("Backup was succesfull!\n");
#endif


#ifdef  LOAD
    list.load();
    list.printcon();
#endif
    return 0;
}



here is my latest edit of the load function:
int List::load()   {
    FILE *fp;
 
    if( (fp = fopen(FILE_NAME, "rb")) == NULL )
        return 1;
    
    /*
    Node new_node;
    int tmp;

    fread(&tmp, sizeof(tmp), 1, fp);
    
    for(int i = 0; i < tmp; i++)	{
	fread(&new_node, sizeof(Node), 1, fp);
	this->add(new_node.i, new_node.d, new_node.s);
    }
	
    */
    int i;
    Node *dummy;
 
    fread(&members, sizeof(members), 1, fp);
    
    dummy = new Node;
    fread(dummy, sizeof(Node), 1, fp);
    list = dummy;
    
    
    for(i = 1, dummy = dummy->next; i < members; i++, dummy = dummy->next)   {
        fread(dummy, sizeof(Node), 1, fp);
	dummy->next = new Node;
    }

    return 0;
}

Was This Post Helpful? 0
  • +
  • -

#14 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3569
  • View blog
  • Posts: 11,089
  • Joined: 05-May 12

Re: Reading and writing a linked list from a file

Posted 28 July 2012 - 09:35 AM

View Postgiwrg98, on 28 July 2012 - 02:30 AM, said:

To test it I run the code in main after I had defined the BACKUP macro:


Ouch!

You do know about command line arguments, right?
Was This Post Helpful? 0
  • +
  • -

#15 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3569
  • View blog
  • Posts: 11,089
  • Joined: 05-May 12

Re: Reading and writing a linked list from a file

Posted 28 July 2012 - 09:45 AM

View Postgiwrg98, on 28 July 2012 - 02:30 AM, said:

here is my latest edit of the load function:
Spoiler

Almost there...

On lines 24-25 you allocate a Node, and read into it. Good. Then there is the beginning of your for loop where you use an old pointer that you read off the disk:
for(i = 1, dummy = dummy->next; ...)



Then there is the other issue: You have member Nodes, yet, you are allocating member+1 Nodes with the way your for loop works.

A little hint: Although in general, pointers that you read from disk are invalid the next time you read it off disk, a null pointer will always be a null pointer because its value is zero.
Was This Post Helpful? 0
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3