473,320 Members | 1,804 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Persistent linked list (node with fixed size)

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
10 5439

"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
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


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

"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
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


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

"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


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

"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
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

5
by: John | last post by:
Hi all, Can a linked list be a member of a structure? If so, when I add or remove an element from the linked list, the size of the structure will change. Will it cause any problem? Thanks a...
19
by: RAJASEKHAR KONDABALA | last post by:
Hi, Does anybody know what the fastest way is to "search for a value in a singly-linked list from its tail" as oposed to its head? I am talking about a non-circular singly-linked list, i.e.,...
1
by: Tim | last post by:
I can't seem to figure out why this very simple linked list wont build.. I mean, there is no intelligence, just add to end. Anyway, please let me know if something i can do will make head (the...
6
by: Jim Showalter | last post by:
I'm trying to write code that gets fixed-length strings from the user and then stores them in a linked list. Here's the definition of my list node: struct node {char str; struct node* next; };...
9
by: Sheldon | last post by:
Hi, I am trying to understand linked lists and the different ways to write a linked list and double linked list. I have been trying to get this function called insert_word to work but to no...
8
by: Jeff Bown | last post by:
Consider implementing a (doubly) linked list. The simplest strategy is to provide functions item_t add_item(item_t predecessor); void delete_item(item_t item); where add_item allocates memory...
8
by: dmp | last post by:
What are Linked list? Please somebody show some ready made programs of linked list
6
by: APEJMAN | last post by:
I know what I'm posting here is wired, but it's been 3 days I'm workin g on these codes, but I have no result I post the code here I dont wanne bother you, but if any one of you have time to...
20
by: sirsnorklingtayo | last post by:
hi guys please help about Linked List, I'm having trouble freeing the allocated memory of a single linked list node with a dynamic char* fields, it doesn't freed up if I use the FREE()...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.