Fabio said:
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:
elFirst()
{
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;
}
