如何在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
}