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

Persistent linked list (node with fixed size)

P: n/a
Hi everyone,

Is there anybody who can suggest me a link where I can find information
about 'Persistent linked list' ?
I need to implement a linked list where every node is a structure like the
following:

struct Node
{
int integer_value;
char test_value[125];
}

The list should be saved on a flat file so that the list can be re-load at
every new start.

Thanks in advance
Fabio
Jul 19 '05 #1
Share this Question
Share on Google+
10 Replies


P: n/a

"Fabio" <fa*************@libero.it> wrote in message
news:bo**********@newsreader.mailgate.org...
Hi everyone,

Is there anybody who can suggest me a link where I can find information
about 'Persistent linked list' ?
I need to implement a linked list where every node is a structure like the
following:

struct Node
{
int integer_value;
char test_value[125];
}


http://www.winghands.it/download/download.html?id=2

Antonio
Jul 19 '05 #2

P: n/a
Are you wanting to actually use this in memory as a linked list? Or an
array? Your struct doesn't have any pointer variables defined in it.

A linked list using your structure might be setup as

struct llNode {
Node myNode;
llNode *prevNode; // points to previous entry in list; NULL if
first entry
llNode *nextNode; // points to next entry in list; NULL if last
entry
};

You would need an additional pointer outside of the structure to point to
the first node in the list, a head pointer;

llNode *headNode;

When loading the file into memory, you would read each record, and execute
your function to insert a new node into the list, passing the headNode and
the Node data into the function.

When saving the linked list to disk, you would traverse the linked list and
write the data in myNode to the file.

Take a look at www.programmersheaven.com . They've got some examples there
that might help.

Paul
When
"Fabio" <fa*************@libero.it> wrote in message
news:bo**********@newsreader.mailgate.org...
Hi everyone,

Is there anybody who can suggest me a link where I can find information
about 'Persistent linked list' ?
I need to implement a linked list where every node is a structure like the
following:

struct Node
{
int integer_value;
char test_value[125];
}

The list should be saved on a flat file so that the list can be re-load at
every new start.

Thanks in advance
Fabio

Jul 19 '05 #3

P: n/a


Fabio wrote:

Hi everyone,

Is there anybody who can suggest me a link where I can find information
about 'Persistent linked list' ?
I need to implement a linked list where every node is a structure like the
following:

struct Node
{
int integer_value;
char test_value[125];
}

The list should be saved on a flat file so that the list can be re-load at
every new start.


What's your specific problem?

In principle this is easy:

write list:
open file
for all nodes
write node
close file
read list:
empty list
open file
as long as there is something to read
read node
insert node into list
close file

Which step(s) give you troubles?`

--
Karl Heinz Buchegger
kb******@gascad.at
Jul 19 '05 #4

P: n/a

"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message
news:3F***************@gascad.at...

What's your specific problem?

In principle this is easy:


I suppose I should have worded my request slightly better.
I'm trying to implement a 'full persistent list'. It means that I cannot
have all nodes in memory but the list must be *only* on a flat file.
So when I have to add a node to the list, I allocate (or re-use) a node in
the flat file. The idea is to have an header with some information such has:
tail, head, free_block and manage a sort of lite persistent heap (witrh
transaction as option)

Fabio
I
Jul 19 '05 #5

P: n/a
Fabio wrote:
"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message
news:3F***************@gascad.at...
What's your specific problem?

In principle this is easy:

I suppose I should have worded my request slightly better.
I'm trying to implement a 'full persistent list'. It means that I cannot
have all nodes in memory but the list must be *only* on a flat file.
So when I have to add a node to the list, I allocate (or re-use) a node in
the flat file. The idea is to have an header with some information such has:
tail, head, free_block and manage a sort of lite persistent heap (witrh
transaction as option)

Fabio
I


One consideration (probably not portable), is to use
the file position instead of pointers.

As far as re-using nodes, that depends on how you
define a node and whether you are using variable
sized records of data.

I decided to implement a persistant linked-list
using the following node:
struct Node
{
streampos data_posn;
streampos next_posn;
streampos prev_posn;
};
The above structure allowed each node to be
a fixed size and the data to be allocated in
the file elsewhere. Since the nodes are fixed
size, they could be re-used.

Note that one platforms value for streampos
may not be the same on another platform.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

Jul 19 '05 #6

P: n/a


Fabio wrote:

"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message
news:3F***************@gascad.at...

What's your specific problem?

In principle this is easy:


I suppose I should have worded my request slightly better.
I'm trying to implement a 'full persistent list'. It means that I cannot
have all nodes in memory but the list must be *only* on a flat file.
So when I have to add a node to the list, I allocate (or re-use) a node in
the flat file. The idea is to have an header with some information such has:
tail, head, free_block and manage a sort of lite persistent heap (witrh
transaction as option)


OK.
Since your nodes have a fixed size, that shouldn't be a problem (add an
entry 'next' to your node, which is used for linking the nodes)

What you suggest above sounds good and would be the way I would do it:
Have 2 chains of nodes: one for used nodes, one for unused nodes, just
like an in-memory list with cached nodes, except that the memory address
is replaced by a "file address" (the things seekg() and tellg() use).

Something like this:
(Note: changing C-based file functions to C++ file functions is left
as an exercise to the read, as well as adding some error checks as well
as adding missing functions)

#include <iostream>
#include <cstring>
using namespace std;

struct MyNode
{
MyNode( int Value = 0, const char* Text = "" ) : m_Value( Value ),
m_Next( 0 )
{ strcpy( m_Text, Text ); }

int m_Value;
char m_Text[128];
long m_Next;
};

struct ListHeader
{
long m_UsedHead;
long m_UsedTail;
long m_UnusedHead;
};

class FileList
{
public:
FileList( const char* szFileName );
~FileList();

long GetHeadPos();
MyNode GetNext( long& Pos );
void Add( const MyNode& Node );
void DelFirst();

protected:
void Enlarge();

ListHeader m_Header;
FILE* m_File;
};

FileList::FileList( const char* szFileName )
{
if( ( m_File = fopen( szFileName, "r+" ) ) == NULL ) {
m_File = fopen( szFileName, "w+" );
m_Header.m_UsedHead = 0;
m_Header.m_UsedTail = 0;
m_Header.m_UnusedHead = 0;
fwrite( &m_Header, sizeof( m_Header ), 1, m_File );
}

else
fread( &m_Header, sizeof( m_Header ), 1, m_File );
}

FileList::~FileList()
{
fseek( m_File, 0, SEEK_SET );
fwrite( &m_Header, sizeof( m_Header ), 1, m_File );
fclose( m_File );
}

long FileList::GetHeadPos()
{
return m_Header.m_UsedHead;
}

MyNode FileList::GetNext( long& Pos )
{
MyNode Temp;

fseek( m_File, Pos, SEEK_SET );
fread( &Temp, sizeof( MyNode ), 1, m_File );

Pos = Temp.m_Next;
return Temp;
}

void FileList::Enlarge()
{
MyNode NewNode;
fseek( m_File, 0, SEEK_END );
m_Header.m_UnusedHead = ftell( m_File );
fwrite( &NewNode, sizeof( NewNode ), 1, m_File );
}

void FileList::Add( const MyNode& Node )
{
MyNode Temp;

if( m_Header.m_UnusedHead == 0 )
Enlarge();

// grab the first unused node and figure out its next field

fseek( m_File, m_Header.m_UnusedHead, SEEK_SET );
fread( &Temp, sizeof( Temp ), 1, m_File );
long NextUnused = Temp.m_Next;

// fill in the data and write the node back

Temp = Node;
Temp.m_Next = 0;
fseek( m_File, m_Header.m_UnusedHead, SEEK_SET );
fwrite( &Temp, sizeof( Temp ), 1, m_File );

// now do the bookkeeping
// the previously unused node gets used and thus
// needs to be chained in the link of used nodes.

if( m_Header.m_UsedHead == 0 ) {
m_Header.m_UsedHead = m_Header.m_UnusedHead;
}
else {
fseek( m_File, m_Header.m_UsedTail, SEEK_SET );
fread( &Temp, sizeof( Temp ), 1, m_File );
Temp.m_Next = m_Header.m_UnusedHead;
fseek( m_File, m_Header.m_UsedTail, SEEK_SET );
fwrite( &Temp, sizeof( Temp ), 1, m_File );
}
m_Header.m_UsedTail = m_Header.m_UnusedHead;

// shorten the list of unused nodes

m_Header.m_UnusedHead = NextUnused;
}

void FileList::DelFirst()
{
if( m_Header.m_UsedHead == 0 )
return;

MyNode Temp;
long FirstPos = m_Header.m_UsedHead;
fseek( m_File, m_Header.m_UsedHead, SEEK_SET );
fread( &Temp, sizeof( Temp ), 1, m_File );
m_Header.m_UsedHead = Temp.m_Next;
Temp.m_Next = m_Header.m_UnusedHead;
fseek( m_File, FirstPos, SEEK_SET );
fwrite( &Temp, sizeof( Temp ), 1, m_File );

m_Header.m_UnusedHead = FirstPos;
}

void PrintList( FileList& List )
{
cout << "********************\n";

long Pos = List.GetHeadPos();
while( Pos ) {
cout << "*** FilePos : " << Pos << "\n";
MyNode Node = List.GetNext( Pos );
cout << Node.m_Value << "\n";
cout << Node.m_Text << endl;
}
}

int main()
{
FileList MyList( "C:\\MyList.dat" );

PrintList( MyList );

MyList.Add( MyNode( 100, "Test1" ) );
MyList.Add( MyNode( 101, "Test2" ) );
MyList.Add( MyNode( 102, "Test3" ) );

PrintList( MyList );

MyList.DelFirst();
MyList.DelFirst();

PrintList( MyList );

MyList.Add( MyNode( 103, "Test4" ) );
MyList.Add( MyNode( 104, "Test5" ) );
MyList.Add( MyNode( 105, "Test6" ) );

PrintList( MyList );

return 0;
}

--
Karl Heinz Buchegger
kb******@gascad.at
Jul 19 '05 #7

P: n/a

"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message
news:3F***************@gascad.at...

Ok...your implementation is similar to what I had in mind.
But whatever structure I use to implement the list on a flat file I probably
need to execute two or more write operations because I update at
least two file pointers. What happen if one write operation fails or the
system crashs ?
Fabio
Jul 19 '05 #8

P: n/a


Fabio wrote:

"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message
news:3F***************@gascad.at...

Ok...your implementation is similar to what I had in mind.
But whatever structure I use to implement the list on a flat file I probably
need to execute two or more write operations because I update at
least two file pointers. What happen if one write operation fails or the
system crashs ?


You end up with an inconsistent file :-)
Ever wondered why database systems cost that much of money?

--
Karl Heinz Buchegger
kb******@gascad.at
Jul 19 '05 #9

P: n/a

"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message
news:3F***************@gascad.at...

You end up with an inconsistent file :-)
Ever wondered why database systems cost that much of money?

You are right Karl...probably I was asking too much...or trying to do
something too complex for my requirements.
Thanks anyway for your help

Fabio
Jul 19 '05 #10

P: n/a
Fabio wrote:
Hi everyone,

Is there anybody who can suggest me a link where I can find information
about 'Persistent linked list' ?
I need to implement a linked list where every node is a structure like the
following:

struct Node
{
int integer_value;
char test_value[125];
}

The list should be saved on a flat file so that the list can be re-load at
every new start.

Thanks in advance
Fabio


I've recently been working on a project for making C++ data structures
persistent. Check out http://visula.org/persist. It uses "mapped
memory", so any modifications you make to your data structure such as a
std::list<> will be mirrored in a file. It's very efficient (i.e. as
fast as RAM) but lacks binary portability.

It's still being 'polished', let me know if you found it useful or if
you encounter problems.

Calum Grant

Jul 19 '05 #11

This discussion thread is closed

Replies have been disabled for this discussion.