How to analyze this FIFO program?

Question

Here are some pieces of the program that completes FIFO buffer pool. I don't know how does it complete. Does anyone help me to analyze it?

This is a struct of FlameHandle, this struct stores total flames, the first frame, and the last frame.

typedef struct FlameHandle{
    PageFlame *first;
    PageFlame *last;
    PageFlame *totalFlames;
    int numWriteIO;
    int numReadIO;
} FlameHandle;

This is a struct of PageFlame, this struct stores info of each flame.

typedef struct PageFlame{
    char *data;
    PageNumber pageNum;
    bool isDirty;
    int fixCount;
    struct PageFlame *next;
    struct PageFlame *prev;
} PageFlame;

This is a struct of BM_BufferPool

typedef struct BM_BufferPool {
    char *pageFile;
    int numPages;   
    ReplacementStrategy strategy;
    void *mgmtData; // use this one to store the bookkeeping info your buffer
    // manager needs for a buffer pool
} BM_BufferPool;

This is a struct of BM_PageHandle

typedef struct BM_PageHandle {
    PageNumber pageNum;
    char *data;
} BM_PageHandle;

This is a function pinPage.

RC pinPage(BM_BufferPool *const bm, BM_PageHandle *const page, const PageNumber pageNum)
{
    FlameHandle *FH;
    FH = bm->mgmtData;
    page->data = (char*)malloc(sizeof(char)*PAGE_SIZE);
    SM_FileHandle fh;
    PageFlame *pf;
    openPageFile(bm->pageFile,&fh);
    page->pageNum = pageNum;
    for(int i=0; i<bm->numPages;i++)
    {
        pf = &(FH->totalFlames)[i];
        if((FH->totalFlames[i]).pageNum == NO_PAGE)
        {
            FH->totalFlames[i].pageNum = pageNum;
            pf->fixCount++;
            ensureCapacity(pageNum+1,&fh);

            //Reads new flame from fh and stores it to (FH->first)->data).
            readBlock(pageNum,&fh,(FH->first)->data); 
            FH->numReadIO++;
            strcpy(page->data,(FH->first)->data);
            FH->last = FH->first;
            if(FH->last->next == NULL)
            {
                FH->first = FH->totalFlames;
            }
            else
            {
                (FH->first) = (FH->last)->next;
            }
            return RC_OK;
        }
    }
}

In this function, It needs to store a new flame in an empty flame (pageNum == NO_PAGE), and at the same time, it needs to keep the FIFO sequence. I really cannot understand the semantics of following code:

if(FH->last->next == NULL){
    FH->first = FH->totalFlames;
}else
{
  (FH->first) = (FH->last)->next;
}

Does anyone can help me?
Here is the link of the whole project on GitHub: https://github.com/randywhisper/assign_cs525/blob/master/assign2/buffer_mgr.c

Answer 1

Remember that the code you pasted there is RS_FIFO.

You can run the code using your pen.

In initBufferPool function, you create a Doubly linked list named PageFlame. PageFlame have N totalPageFlames.

PageFlame's fist points to totalPageFlames[0], last points to end.

---

FIFO is first in first out.

Suppose you have a PageFlame(length 4) like a,b,c,d.

Here comes your snippet code.

FH->last = FH->first, last->next is b, not NULL, so goes to (FH->first) = (FH->last)->next;. That means , last points to a while first points to b.

---

Next run, last points to b while first points to c.

a is read first and then first moves to next one b.

I think this is clear.

---

When there is only one element d and d->next is NULL. So first will move from last out element c to d. When next element e comes in the queue, first will move to the e and last stay in d.

RS_FIFO, first in first out. That is it.