copy (3) of pagingexample.cpp

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

// ****************************************************************************
// PagingExample.cpp
//
// Example implementation of object paging.
//
// (c) Charles Weir, James Noble 2000
// 
// ****************************************************************************

#include <fstream>
#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;


class ObjectWithPagedData {
    // A Base class for an object that can page its data out to file.  The data
    // must always be accessed using the GetPagedData calls.
private:
    PageFile& pageFile;
    const int offsetOfDataInFile;
protected:
    const void* GetPagedData() const;
    void* GetPagedData();
    ObjectWithPagedData(PageFile& thePageFile);
    ~ObjectWithPagedData();
    friend int main();
};  

class PageFrame 
// A single page of 'real memory', representing the page of virtual memory starting
// at StartOffset()
{
    friend class PageFile;
    enum { INVALID_FILE_OFFSET = -1 };

 private:
    bool  dirtyFlag;   
    int   offsetOfCurrentPageInFile;
    void* bufferContainingCurrentPage;

 public:
    PageFrame( int pageSize );
    ~PageFrame();

    int StartOffset();
    bool InUse();
    const void* PageFrame::GetConstPage();
    void* GetWritablePage();
};


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.
private:
    vector<PageFrame*> pageTable;       
    vector<PageFrame*> pageFrameArray;      
    int pageSize;
    fstream fileStream;
    list<int> listOfOffsetsOfFreePages; 

public: 
    PageFile( char* fileName, int pageSizeInBytes, int nPagesInCache );
    ~PageFile();

    int PageSize() { return pageSize; }
    void Flush();

private: 
    friend class ObjectWithPagedData;

    PageFrame* FindPageFrameForOffset( int offset );
    PageFrame* NewPage();
    PageFrame* MakeFrameAvailable();
    void DeletePage(int offsetOfPageInFile);
    void SaveFrame( PageFrame* frame );
    void LoadFrame( PageFrame* frame, int fileOffset );

  // Debugging information:
    friend int main();
    int PageFaults;
    int PageWrites;
    void Invariant(bool flushed=false);
};

// ****************************************************************************
// ObjectWithPagedData
// ****************************************************************************

const void* ObjectWithPagedData::GetPagedData() const { 
    PageFrame* frame = pageFile.FindPageFrameForOffset( offsetOfDataInFile );
    return frame->GetConstPage();
}

void* ObjectWithPagedData::GetPagedData() { 
    PageFrame* frame = pageFile.FindPageFrameForOffset( offsetOfDataInFile );
    return frame->GetWritablePage();
}

ObjectWithPagedData::ObjectWithPagedData(PageFile& thePageFile)
    : pageFile( thePageFile ), 
      offsetOfDataInFile( thePageFile.NewPage()->StartOffset() ) 
{}

ObjectWithPagedData::~ObjectWithPagedData() {
    pageFile.DeletePage(offsetOfDataInFile);
}

// ****************************************************************************
// PageFile
// ****************************************************************************

PageFile::PageFile( char* fileName, int pageSizeInBytes, int nPagesInCache )
    : fileStream( fileName, 
                  ios::in| ios::out | ios::binary | ios::trunc),
      pageSize( pageSizeInBytes ),
      PageFaults(0), PageWrites(0) {
    ASSERT( fileStream.good() );
    for (int i = 0; i<nPagesInCache; i++) {
        pageFrameArray.push_back( new PageFrame( pageSize ) );
    }
}

PageFile::~PageFile() {
    for (vector<PageFrame*>::iterator i = pageFrameArray.begin();
         i != pageFrameArray.end(); i++ )
        delete *i;
    fileStream.close();
}

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

void PageFile::LoadFrame( PageFrame* frame, int fileOffset ) {
    int newPos = fileStream.rdbuf()->pubseekoff( fileOffset, ios::beg );
    ASSERT( newPos == fileOffset );
    fileStream.read( (char*)frame->bufferContainingCurrentPage, PageSize() );
    ASSERT( fileStream.gcount() == PageSize() );
    frame->offsetOfCurrentPageInFile = fileOffset;
    PageFaults++;
}

void PageFile::SaveFrame( PageFrame* frame ) {
    if (frame->dirtyFlag) {
        int newPos = fileStream.rdbuf()->pubseekoff( frame->StartOffset(), ios::beg );
        ASSERT( newPos == frame->StartOffset() );
        fileStream.write( (char*)frame->bufferContainingCurrentPage, pageSize );
        PageWrites++;
        frame->dirtyFlag = false;
    }
    pageTable[frame->StartOffset()/pageSize] = 0;
    frame->offsetOfCurrentPageInFile = PageFrame::INVALID_FILE_OFFSET;
}

PageFrame* PageFile::NewPage() {
    // Create a new object, either from the free queue or by adding a new
    // Entry to page table 
    PageFrame* frame;
    if (!listOfOffsetsOfFreePages.empty()) {
        int offset=listOfOffsetsOfFreePages.front();
        listOfOffsetsOfFreePages.pop_front();
        frame=FindPageFrameForOffset( offset );
    } else {
        frame = MakeFrameAvailable();
        frame->offsetOfCurrentPageInFile = pageTable.size() * pageSize;
        pageTable.push_back( frame );
        // Need to ensure the file is big enough for random access
        fileStream.write( (char*)frame->bufferContainingCurrentPage, pageSize );
    }
    Invariant();
    return frame;
}

void PageFile::DeletePage(int offsetOfPageInFile) {
    listOfOffsetsOfFreePages.push_front(offsetOfPageInFile);
    Invariant();
}

PageFrame* PageFile::FindPageFrameForOffset( int offsetOfPageInFile ) {
    // Finds a real memory page corresponding to the given virtual offset.  If it's already 
    // cached, returns it, otherwise co-opts a page and loads the page from disk.
    int pageNumber = offsetOfPageInFile / pageSize;
    ASSERT( pageNumber < pageTable.size() );
    PageFrame* frame = pageTable[pageNumber];
    if (frame == 0) {
        frame = MakeFrameAvailable();
        LoadFrame( frame, offsetOfPageInFile );
        pageTable[pageNumber] = frame;
    }
    ASSERT( frame->offsetOfCurrentPageInFile == offsetOfPageInFile );
    Invariant();
    return frame;
}

PageFrame* PageFile::MakeFrameAvailable() {
    PageFrame* frame = pageFrameArray[ (rand() * pageFrameArray.size()) / RAND_MAX ]; 
    if (frame->InUse()) {
        SaveFrame( frame ); 
    }
    Invariant();
    return frame;
}

void PageFile::Flush() {
    // Save all cached page frames.
    for (vector<PageFrame*>::iterator i = pageFrameArray.begin();
         i != pageFrameArray.end(); i++ ) {
        SaveFrame( *i ); 
    }
    Invariant(true);
}

// ****************************************************************************
// Page Frame 
// ****************************************************************************

PageFrame::PageFrame( int pageSize )
    : bufferContainingCurrentPage( new char[pageSize] ),
      dirtyFlag( false ),
      offsetOfCurrentPageInFile(PageFrame::INVALID_FILE_OFFSET)
{}

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

const void* PageFrame::GetConstPage() { 
    return bufferContainingCurrentPage; 
}

void* PageFrame::GetWritablePage() { 
    dirtyFlag = true; 
    return bufferContainingCurrentPage;
}

int PageFrame::StartOffset() { 
    return offsetOfCurrentPageInFile; 
}
bool PageFrame::InUse() { 
    return offsetOfCurrentPageInFile != INVALID_FILE_OFFSET; 
}

// ****************************************************************************
// Example Code
// ****************************************************************************


typedef char Pixel;
enum { SCREEN_HEIGHT = 10, SCREEN_WIDTH = 10 };  // Keep it small for testing.

class BitmapImageData {
    friend class BitmapImage;
    Pixel pixels[SCREEN_HEIGHT * SCREEN_WIDTH];
};

class BitmapImage : public ObjectWithPagedData {
private:
    BitmapImageData* GetData() 
        { return (BitmapImageData*)GetPagedData(); }
    const BitmapImageData* GetData() const 
        { return (const BitmapImageData*)GetPagedData(); }
public:
    BitmapImage( PageFile& thePageFile )
        : ObjectWithPagedData(thePageFile) {
        memset( GetData(), 0, sizeof( BitmapImageData) ); 
    }
    Pixel GetPixel(int pixelNumber) const { 
        return GetData()->pixels[pixelNumber]; 
    }
    void SetPixel(int pixelNumber, Pixel newValue) { 
        GetData()->pixels[pixelNumber] = newValue; 
    }
};


// ****************************************************************************
// Test Code
// ****************************************************************************


int main() {
    const int N_IMAGES = 10;
    PageFile pageFile("testfile.dat", sizeof( BitmapImageData ), 4 );
    vector<BitmapImage*> imageVector;
    
    int i;
    for (i = 0; i<N_IMAGES; i++)
        imageVector.push_back( new BitmapImage(pageFile) );
  
    ASSERT( pageFile.PageFaults == 0 );
    ASSERT( pageFile.PageWrites > 0 );
    pageFile.Flush();
    ASSERT( pageFile.PageWrites == N_IMAGES );

    for (i = 0; i<N_IMAGES; i++)
        imageVector[i]->SetPixel(1, i);

    ASSERT( pageFile.PageFaults == N_IMAGES );
    ASSERT( pageFile.PageWrites > N_IMAGES );
    pageFile.Flush();
    ASSERT( pageFile.PageWrites == 2*N_IMAGES );

    for (i = 0; i<N_IMAGES; i++)
        ASSERT( imageVector[i]->GetPixel(1) == i );

    ASSERT( pageFile.PageWrites == 2*N_IMAGES );
    pageFile.Flush();
    ASSERT( pageFile.PageWrites == 2*N_IMAGES );

    // Deletion test.
    BitmapImage*& image = imageVector[0];
    int deletedObjectOffset = image->offsetOfDataInFile;
    delete image;
    image = new BitmapImage( pageFile );
    ASSERT( image->offsetOfDataInFile == deletedObjectOffset );
    
    for (i = 0; i<N_IMAGES; i++)
        delete imageVector[i];
    
    ASSERT( pageFile.listOfOffsetsOfFreePages.size() == N_IMAGES );
    cout << "All Tests worked" << endl;
    PAUSE();
    return 0;
}