如何在C中实现循环列表(环形缓冲区)？

如何实现一个循环列表,当它填满时覆盖最旧的条目？

对于一点背景,我想在GWT中使用循环列表; 所以使用第三方库不是我想要的.

1> Adam Davis..：

---

一个非常简单的实现,用C表示.实现循环缓冲区样式的FIFO队列.通过创建包含队列大小,队列数据和队列索引(输入和输出)的结构可以使其更通用,该结构将与要添加或从队列中删除的数据一起传入.然后,这些相同的例程可以处理多个队列.另请注意,这允许任何大小的队列,但如果使用2的幂并进一步自定义代码,则可以使用加速.

/* Very simple queue
 * These are FIFO queues which discard the new data when full.
 *
 * Queue is empty when in == out.
 * If in != out, then 
 *  - items are placed into in before incrementing in
 *  - items are removed from out before incrementing out
 * Queue is full when in == (out-1 + QUEUE_SIZE) % QUEUE_SIZE;
 *
 * The queue will hold QUEUE_ELEMENTS number of items before the
 * calls to QueuePut fail.
 */

/* Queue structure */
#define QUEUE_ELEMENTS 100
#define QUEUE_SIZE (QUEUE_ELEMENTS + 1)
int Queue[QUEUE_SIZE];
int QueueIn, QueueOut;

void QueueInit(void)
{
    QueueIn = QueueOut = 0;
}

int QueuePut(int new)
{
    if(QueueIn == (( QueueOut - 1 + QUEUE_SIZE) % QUEUE_SIZE))
    {
        return -1; /* Queue Full*/
    }

    Queue[QueueIn] = new;

    QueueIn = (QueueIn + 1) % QUEUE_SIZE;

    return 0; // No errors
}

int QueueGet(int *old)
{
    if(QueueIn == QueueOut)
    {
        return -1; /* Queue Empty - nothing to get*/
    }

    *old = Queue[QueueOut];

    QueueOut = (QueueOut + 1) % QUEUE_SIZE;

    return 0; // No errors
}

---

@RocketRoy代码是正确的.它会在缓冲区中的单个空间进行交换,以进行更简单的空/完全测试.

---

如果我错了,请纠正我,但是这不允许你只存储99个条目吗？表达式(在==(out-1 + SIZE)%SIZE中)表示如果in是一个在out之前.但是还没有写过,所以第100个点从未被写入.

---

@AdamDavis代码不直观与不正确无关.此实现具有指定的"QUEUE_ELEMENTS"数,并在所有边缘情况下生成正确的结果,并且具有比您的实现更少的簿记变量.简单有效.

---

@RocketRoy我不同意你的意见.虽然还有其他方法可以实现具有FIFO功能的循环列表,但此代码并不正确,并且确实有效.它确实留下了一个向后爬过缓冲区的漏洞,但这是设计的,并且是实现FIFO的一种非常时间/处理的有效方式.我还简要回顾了你建议的代码更好,并且在这一点上也不同意,但似乎其他人在那里发表评论,提出了许多观点.我在这个答案中提供的实现并不完美,但它很简单,易懂,而且有效.