如何分析这个FIFO程序呢？

Question

这里是完成FIFO缓冲池的部分程序。我不知道它是如何完成的。有人帮我分析一下吗？

这是FlameHandle的一个结构体，这个结构体存储了总火焰数、第一帧和最后一帧。

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

这是PageFlame的一个结构体，这个结构体存储了每个火焰的信息。

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

这是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;

这是BM_PageHandle

的结构

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

这是一个函数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;
        }
    }
}

在这个函数中，需要在一个空的flame(pageNum == NO_PAGE)中存储一个新的flame，同时需要保持FIFO顺序。我真的无法理解以下代码的语义：

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

有人能帮帮我吗？
这是 GitHub 上整个项目的 link： https://github.com/randywhisper/assign_cs525/blob/master/assign2/buffer_mgr.c

Answer 1

请记住，您粘贴的代码是 RS_FIFO。

您可以运行使用笔输入代码。

在 initBufferPool 函数中，您创建了一个名为 PageFlame 的 Doubly linked list。 PageFlame 有 N totalPageFlames.

PageFlame的拳头指向totalPageFlames[0]，last指向终点

FIFO先进先出。

假设您有一个 PageFlame（长度 4），例如 a,b,c,d。

这是您的代码段。

FH->last = FH->first，last->next 是 b，不是 NULL，所以转到 (FH->first) = (FH->last)->next;。也就是说，last 指向了 while first 指向了 b.

下一个运行，last指向b而first指向c。

a 先读，然后 first 移动到下一个 b。

我想这很清楚。

只有一个元素d且d->next为NULL时。所以 first 将从最后一个元素 c 移动到 d。当下一个元素 e 进入队列时，第一个将移动到 e 最后一个留在 d.

RS_FIFO，先进先出。就是这样。

如何分析这个FIFO程序呢？

How to analyze this FIFO program?

c

buffer

pool

fifo