pagingexamplewithkevlinspointer.cpp

内存受限系统软件开发一书的代码。（虽不及Gang of Four的模式掷地有声

#include <fstream>
//#include <string>
#include <vector>
#include <list>
#include <iostream>
#include <deque>

#define PAUSE() (cin.get(),cin.get())

//#define PAUSE() (1)

#define ASSERT( x ) ((x) ? 0 : &(cout << #x ": Failed: " __FILE__ " " << __LINE__ << endl) && PAUSE() )
#define SAY( x ) (cout << x)

using namespace :: std;


class PageFile;

template <class T> class POPointer {
public:
  POPointer( T* obj=0 ) : offset( obj ? obj->GetOffset() : -1 ) {}
  
  //  const POPointer<T>& operator=( const POPointer<T>&b ) const
  //  { offset = b.offset; return *this;}

  template<class U>
  POPointer & operator=(const POPointer<U> & rhs)
    {
      offset = rhs.offset;
      return *this;
    }
  
  template<class U>
  POPointer(const POPointer<U> & rhs)
    : offset( rhs.offset ) {}
  
  operator bool() const { return offset != -1; }

  const T* operator ->() const { return obj=(T*)GetConst(); }
  T* operator ->() { return obj=Get(); }

  void Delete() 
    { if (*this) delete Get(); }

private:
  T* Get();
  const T* GetConst() const;
  mutable int offset;
  friend int main();
};

class PageFile; 

class PagedObject {
public:
  void* operator new( unsigned int size );
  void operator delete( void* item );

  int GetOffset() { return offset; }
private:
  friend class PageFile;
  friend class PageFrame;

  void SetOffset( int i ) { offset=i; }
  int offset;
public:
  static PageFile& File;
};

class PageFrame 
// A single page of 'real memory', representing the page of virtual memory starting
// at StartOffset()
{
 public:
  PageFrame( int pageSize );
  ~PageFrame();

  const PagedObject* GetConstObject() { 
    ASSERT( m_Offset == m_Object->GetOffset() );
    return m_Object; 
  }

  PagedObject* GetObject() { 
    m_Dirty = true; 
    return const_cast<PagedObject*> (GetConstObject()); 
  }

  void Load( PageFile& file, int fileOffset );
  void Save( PageFile& file );
  int StartOffset() { return m_Offset; }
 private:
  friend class PageFile; friend class PagedObject;
  bool m_Dirty;           // Set if the page has been written
  int m_Offset;                 // Equal to m_Object->GetOffset() only
                                // when page is loaded
  PagedObject* m_Object;
};


class PageFile
// A buffer which holds only a fixed portion of itself in RAM, and pages
// the remainder to and from a temporary file on secondary storage.
{
public: 
  PageFile( int pageSize, int pageCacheSize );
  ~PageFile();

  int PageSize() { return m_PageSize; }
  const PagedObject* GetConstObject(int offset) 
    { return FindPageFor( offset )->GetConstObject(); }
  PagedObject* GetObject(int offset) 
    { return FindPageFor( offset )->GetObject(); }
  void Flush();
private: 
  friend class PageFrame;
  friend class PagedObject;

  PageFrame* FindPageFor( int offset );
  PageFrame* NewPage();
  PageFrame* MakeFrameAvailable();
  void DeletePage( PageFrame* pf );
  void FrameUsed( PageFrame* pf );

  // Utility functions to read and write bytes to file:
  void Read( char* buffer, int offset, int nBytes );
  void Write( char* buffer, int offset, int nBytes );
  
  vector<PageFrame*> m_PageTable;       
  // Entry for each virtual memory page, Null if not loaded, indexed
  // by (fileOffset/PageSize)

  list<PageFrame*> m_PageFrames;      
  // Entry for each 'real memory' page; max m_PageCacheSize entries.
  int m_PageSize;
  int m_PageCacheSize;
  fstream m_File;

  list<int> m_FreeList;  // List of file offsets

  // Debugging information:
  friend int main();
  int m_PageFaults;
  int m_PageWrites;
  int m_CacheHits;
  void Invariant(bool flushed=false);
};

template <class T>
const T* POPointer<T>::GetConst() const { 
  return (const T*)PagedObject::File.GetConstObject( offset );
}  

template <class T>
T* POPointer<T>::Get() { 
  return (T*)PagedObject::File.GetObject( offset ); 
}

void* PagedObject::operator new( unsigned int size )
{ 
  SAY("PagedObject::new" << size << endl);
  ASSERT( size <= File.PageSize() );
  return File.NewPage()->GetObject(); 
}

void PagedObject::operator delete( void* item )
{
  PageFrame* pf = File.FindPageFor(((PagedObject*)item)->GetOffset());
  //  pf->m_Dirty = true;
  File.DeletePage( pf );
}


PageFile::PageFile( int pageSize, int pageCacheSize )
  : m_File( "TestFile.dat", 
            ios::in| ios::out | ios::binary | ios::trunc),
    m_PageSize( pageSize ),
    m_PageCacheSize( pageCacheSize ),
    m_PageFaults(0), m_PageWrites(0), m_CacheHits(0)
{
  ASSERT( m_File.good() );
}

PageFile::~PageFile()
{
  for (list<PageFrame*>::iterator i = m_PageFrames.begin();
       i != m_PageFrames.end(); i++ )
    delete *i;
  m_File.close();
}

void PageFile::Invariant(bool flushed)
{
  for (int i = 0; i< m_PageTable.size(); i++)
    if (flushed)
      ASSERT( m_PageTable[i] == 0 );
    else
      ASSERT( m_PageTable[i] == 0 || m_PageTable[i]->StartOffset() == i*m_PageSize );
}

void PageFile::Read( char* buffer, int offset, int nBytes )
  // Utility function, to read bytes from the page file at the given offset.
{ 
  int newPos = m_File.rdbuf()->pubseekoff( offset, ios::beg );
  ASSERT( newPos == offset );
  m_File.read( buffer, nBytes );
  ASSERT( m_File.gcount() == nBytes );
  m_PageFaults++;
}

void PageFile::Write( char* buffer, int offset, int nBytes ) 
  // Utility function to write bytes to the page file at the given offset.
{
  int newPos = m_File.rdbuf()->pubseekoff( offset, ios::beg );
  ASSERT( newPos == offset );
  m_File.write( buffer, nBytes );
  m_PageWrites++;
}

PageFrame* PageFile::NewPage() {
  // Create a new object, either from the free queue or by adding a new
  // Entry to page table 
  PageFrame* pf;
  if (!m_FreeList.empty())
    {
      int offset=m_FreeList.front();
      m_FreeList.pop_front();
      pf=FindPageFor( offset );
    }
  else
    {
      pf = MakeFrameAvailable();
      pf->m_Offset = m_PageTable.size() * m_PageSize;
      pf->m_Object->SetOffset( pf->m_Offset );
      m_PageTable.insert( m_PageTable.end(), pf );
      pf->Save( *this );  // Need to ensure the file is big enough for random access
    }
  Invariant();
  pf->m_Dirty = true;
  return pf;
}

void PageFile::DeletePage( PageFrame* pf )
{
  m_FreeList.push_front( pf->StartOffset() );
  Invariant();
}

PageFrame* PageFile::FindPageFor( int offset )
  // Finds a real memory page corresponding to the given virtual offset.  If it's already 
  // cached, returns it, otherwise co-opts the LRU and loads the page from disk.
{
  int pageNumber = offset / m_PageSize;
  ASSERT( pageNumber < m_PageTable.size() );
  PageFrame* frame = m_PageTable[pageNumber];
  if (frame == 0) 
    {
      frame = MakeFrameAvailable();
      frame->Load( *this, offset );
      m_PageTable[pageNumber] = frame;
      ASSERT( frame->m_Offset == offset );
    }
  else
    {
      FrameUsed( frame );
      m_CacheHits++;
    }
  ASSERT( frame->m_Offset == offset );
  Invariant();
  return frame;
}

void PageFile::FrameUsed( PageFrame* pf )
{
  m_PageFrames.remove( pf ); 
  m_PageFrames.push_back( pf ); 
}

PageFrame* PageFile::MakeFrameAvailable()
{
  PageFrame* pf;
  if (m_PageFrames.size() < m_PageCacheSize)
    {
      pf = new PageFrame( m_PageSize );
      m_PageFrames.push_back( pf );
    }
  else
    {
      pf = m_PageFrames.front(); 
      FrameUsed( pf );
      pf->Save( *this ); 
      m_PageTable[pf->StartOffset()/m_PageSize] = 0;
    }
  Invariant();
  return pf;
}

void PageFile::Flush()
  // Save all cached page frames.
{
  for (list<PageFrame*>::iterator i = m_PageFrames.begin();
       i != m_PageFrames.end(); i++ )
    {
      (*i)->Save( *this ); 
      m_PageTable[(*i)->StartOffset()/m_PageSize] = 0;
    }
  Invariant(true);
}

PageFrame::PageFrame( int pageSize )
  : m_Object( (PagedObject*)(new char[pageSize]) ),
    m_Dirty( false )
{}

PageFrame::~PageFrame()
{
  delete [] (char*)(m_Object);
}

void PageFrame::Load( PageFile& file, int fileOffset )
  // Make me be the virtual memory page corresponding to fileOffset 
{
  ASSERT( !m_Dirty );
  (void)file.Read( (char*)m_Object, fileOffset, 
                   file.PageSize() );
  ASSERT( m_Object->GetOffset() == fileOffset );
  m_Offset = fileOffset;
}

void PageFrame::Save( PageFile& file ) 
{
  if (m_Dirty)
    file.Write( (char*)m_Object, m_Object->GetOffset(), file.PageSize() );
  m_Dirty = false;
}


// ****************************************************************************

// Test code for Paged Objects.

class MyObject2 : public PagedObject {
public: 
  typedef POPointer<MyObject2> Ptr;
  MyObject2( int i ) : val( i ) {cout << "MyObject2: " << i << " " << val << endl;}
  ~MyObject2() { 
    SAY( "~MyObject2: " << val << "\n" ); 
  }
  int val;
};

class MyObject : public PagedObject {
public: 
  typedef POPointer<MyObject> Ptr;
  
  MyObject( Ptr p, int i); 
  ~MyObject() 
    {
      const Ptr self = this;
      SAY( "~MyObject\n" ); 
      self->other.Delete(); 
      self->next.Delete(); 
    }

  MyObject2::Ptr other;
  Ptr next;
};

MyObject::MyObject( MyObject::Ptr p, int i ) 
  : next( p ), other( new MyObject2( i ) )  
{cout <<"MyObject: " << i << " " << other->val << endl; PAUSE(); }

PageFile& PagedObject::File = *new PageFile( sizeof( MyObject ), 4 );



int main( )
{
  PageFile& f = PagedObject::File;

  MyObject::Ptr queue;
  
  const MyObject::Ptr x = queue;
  const MyObject::Ptr r = x;
  ASSERT( r.offset == -1 );

  int i=0;
  for (; i<6; i++) {
    queue = new MyObject( queue, i );
    cout << "queue->other->val" << queue->other->val << endl;
  };
  
  ASSERT( f.m_PageFaults == 0 );
  ASSERT( f.m_PageWrites > 0 );
  f.Flush();
  ASSERT( f.m_PageWrites == 12 );

  const MyObject::Ptr p1 = queue;

  cout << "p1->other->val" << p1->other->val << endl;

  ASSERT( p1->other->val == 5 );
  f.Flush();
  ASSERT( f.m_PageFaults == 2 
          && f.m_PageWrites == 12);

  for (const MyObject::Ptr p( queue ); p; p=p->next ) 
    {
      i--;
      ASSERT( p->other->val == i &&
              p->other->val == i );
    }
  ASSERT( f.m_CacheHits > 6 && f.m_PageWrites == 12 &&
          f.m_PageFaults > 6);

  queue->other->val = 999;
  f.Flush();
  ASSERT( f.m_PageWrites == 14 );

  // Testing deletion:

  queue.Delete();
  queue = 0;
  ASSERT( f.m_FreeList.size() == 12 );
  f.Flush();
  ASSERT( f.m_PageWrites >= 26 );
  for (i=0; i<6; i++)
    queue = new MyObject( queue, i );
  ASSERT( f.m_FreeList.size() == 0 );
  f.Flush();
  ASSERT( f.m_PageWrites >= 38 );
  
  cout << "All Tests worked" << endl;
  PAUSE();
  return 0;
}