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

Question

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

关于一些背景知识，我想在 GWT 中使用循环列表；所以使用第三方库不是我想要的。

Answer 1

一个非常简单的实现，用 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
}