如何在 C 中实现循环列表(环形缓冲区)? [英] How do I implement a circular list (ring buffer) in C?

问题描述

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

How do I implement a circular list that overwrites the oldest entry when it's full?

作为背景知识，我想在 GWT 中使用循环列表；所以使用 3rd 方库 不是我想要的.

For a little background, I want to use a circular list within GWT; so using a 3rd party lib is not what I want.

推荐答案

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

A very simple implementation, expressed in C. Implements a circular buffer style FIFO queue. Could be made more generic by creating a structure containing the queue size, queue data, and queue indexes (in and out), which would be passed in with the data to add or remove from the queue. These same routines could then handle several queues. Also note that this allows queues of any size, although speedups can be used if you use powers of 2 and customize the code further.

/* 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
}

这篇关于如何在 C 中实现循环列表(环形缓冲区)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！