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
}

Answer 2

固定長の循環リストが必要な場合。(動的) 配列を使用できます。ハウスキーピングには 2 つの変数を使用します。1 つは次の要素の位置、もう 1 つは要素の数をカウントします。

Put: 要素を自由な場所に置きます。位置を移動します (モジュロ長さ)。count がリストの長さと等しくない限り、count に 1 を追加します。Get: count>0 の場合のみ。位置を左に移動します (モジュロ長さ)。カウントを減らします。

Answer 3

リンクされたリストを使用します。頭と尾に別々のポインターを維持します。リストの先頭からポップし、末尾にプッシュします。円形にしたい場合は、新しい尾が常に頭を向いていることを確認してください。

リンクされたリストを使用して FIFO を実装したい理由は理解できますが、なぜそれを循環リストにするのでしょうか?

Answer 4

これをマイクロコントローラに使用しています。コードを簡単にするために、1 バイトは埋められません。別名サイズ - 1 は、実際にはフル容量です。

fifo_t* createFifoToHeap(size_t size)
{
    byte_t* buffer = (byte_t*)malloc(size);

    if (buffer == NULL)
        return NULL;

    fifo_t* fifo = (fifo_t*)malloc(sizeof(fifo_t));

    if (fifo == NULL)
    {
       free(buffer);
       return NULL;
    }

    fifo->buffer = buffer;
    fifo->head = 0;
    fifo->tail = 0;
    fifo->size = size;

    return fifo;
}

#define CHECK_FIFO_NULL(fifo) MAC_FUNC(if (fifo == NULL) return 0;)

size_t fifoPushByte(fifo_t* fifo, byte_t byte)
{
    CHECK_FIFO_NULL(fifo);

    if (fifoIsFull(fifo) == true)
       return 0;

    fifo->buffer[fifo->head] = byte;

    fifo->head++;
    if (fifo->head == fifo->size)
       fifo->head = 0;

    return 1;
}

size_t fifoPushBytes(fifo_t* fifo, byte_t* bytes, size_t count)
{
    CHECK_FIFO_NULL(fifo);

    for (uint32_t i = 0; i < count; i++)
    {
        if (fifoPushByte(fifo, bytes[i]) == 0)
            return i;
    }

    return count;
}

size_t fifoPopByte(fifo_t* fifo, byte_t* byte)
{
    CHECK_FIFO_NULL(fifo);

    if (fifoIsEmpty(fifo) == true)
        return 0;

    *byte = fifo->buffer[fifo->tail];

    fifo->tail++;
    if (fifo->tail == fifo->size)
        fifo->tail = 0;

    return 1;
}

size_t fifoPopBytes(fifo_t* fifo, byte_t* bytes, size_t count)
{
    CHECK_FIFO_NULL(fifo);

    for (uint32_t i = 0; i < count; i++)
    {
        if (fifoPopByte(fifo, bytes + i) == 0)
            return i;
    }

    return count;
}

bool fifoIsFull(fifo_t* fifo)
{
    if ((fifo->head == (fifo->size - 1) && fifo->tail == 0) || (fifo->head == (fifo->tail - 1)))
        return true;
    else
        return false;
}

bool fifoIsEmpty(fifo_t* fifo)
{
    if (fifo->head == fifo->tail)
        return true;
    else
        return false;
}

size_t fifoBytesFilled(fifo_t* fifo)
{
    if (fifo->head == fifo->tail)
        return 0;
    else if ((fifo->head == (fifo->size - 1) && fifo->tail == 0) || (fifo->head == (fifo->tail - 1)))
        return fifo->size;
    else if (fifo->head < fifo->tail)
        return (fifo->head) + (fifo->size - fifo->tail);
    else
        return fifo->head - fifo->tail; 
}

Answer 5

配列を使用し、変数 P を使用可能な最初の位置に保持します。

新しい要素を追加するたびに P を増やします。

配列内の P の同等のインデックスを知るには、(P % n) を実行します。ここで、n は配列のサイズです。

Answer 6

queue がキャッシュを作成する最良の方法だとは思いません。あなたは本当に速くなるためにあなたのキャッシュになりたいです! また、キャッシュを非常に小さくしたい場合やメモリが非常に限られている場合を除き、キューの線形スキャンを実行する方法はありません。

非常に小さなキャッシュや遅いキャッシュが必要ないと仮定すると、リンク リスト内のノードへの値のハッシュ マップを持つリンク リストを使用するのが適切な方法です。ヘッドはいつでも追い出すことができ、要素がアクセスされるたびに、それを削除してリストのヘッドに入れることができます。アクセスするには、直接取得するか、O(1) のキャッシュにあるかどうかを確認できます。要素の削除も O(1) であり、リストの更新も同様です。

例として、Java の LinkedHashMap を見てください。

http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHashMap.html

Answer 7

これは、 javaを使用して動的に増加/減少する循環キューを作成するエレガントな方法です。

簡単かつ迅速に理解できるように、コードの大部分にコメントを付けました。それが役に立てば幸い ：）

    public class CircularQueueDemo {
    public static void main(String[] args) throws Exception {

        CircularQueue queue = new CircularQueue(2);
        /* dynamically increasing/decreasing circular queue */
        System.out.println("--dynamic circular queue--");
        queue.enQueue(1);
        queue.display();
        queue.enQueue(2);
        queue.display();
        queue.enQueue(3);
        queue.display();
        queue.enQueue(4);
        queue.display();
        queue.deQueue();
        queue.deQueue();
        queue.enQueue(5);
        queue.deQueue();    
        queue.display();

    }
}

class CircularQueue {
    private int[] queue;
    public int front;
    public int rear;
    private int capacity;

    public CircularQueue(int cap) {
        front = -1;
        rear = -1;
        capacity = cap;
        queue = new int[capacity];
    }

    public boolean isEmpty() {
        return (rear == -1);
    }

    public boolean isFull() {
        if ((front == 0 && rear == capacity - 1) || (front == rear + 1))
            return true;
        else
            return false;
    }

    public void enQueue(int data) { 
        if (isFull()) {            //if queue is full then expand it dynamically   
            reSize();                    
            enQueue(data);
        } else {                                 //else add the data to the queue
            if (rear == -1)                      //if queue is empty
                rear = front = 0;
            else if (rear == capacity)          //else if rear reached the end of array then place rear to start (circular array)
                rear = 0;
            else
                rear++;                         //else just incement the rear 
            queue[rear] = data;                 //add the data to rear position
        }
    }

    public void reSize() {
        int new_capacity = 2 * capacity;                  //create new array of double the prev size
        int[] new_array = new int[new_capacity];          

        int prev_size = getSize();                        //get prev no of elements present
        int i = 0;                                        //place index to starting of new array

        while (prev_size >= 0) {                          //while elements are present in prev queue
            if (i == 0) {                                 //if i==0 place the first element to the array
                new_array[i] = queue[front++];
            } else if (front == capacity) {               //else if front reached the end of array then place rear to start (circular array) 
                front = 0;
                new_array[i] = queue[front++];
            } else                                        //else just increment the array
                new_array[i] = queue[front++];
            prev_size--;                                  //keep decreasing no of element as you add the elements to the new array
            i++;                                          //increase the index of new array
        }
        front = 0;                                        //assign front to 0
        rear = i-1;                                       //assign rear to the last index of added element
        capacity=new_capacity;                            //assign the new capacity
        queue=new_array;                                  //now queue will point to new array (bigger circular array)
    }

    public int getSize() {
        return (capacity - front + rear) % capacity;                  //formula to get no of elements present in circular queue
    }

    public int deQueue() throws Exception {
        if (isEmpty())                                       //if queue is empty
            throw new Exception("Queue is empty");
        else {
            int item = queue[front];                        //get item from front
            if (front == rear)                              //if only one element
                front = rear = -1;
            else if (front == capacity)                     //front reached the end of array then place rear to start (circular array)
                front = 0;
            else
                front++;                                    //increment front by one
            decreaseSize();                                 //check if size of the queue can be reduced to half
            return item;                                    //return item from front
        }

    }

    public void decreaseSize(){                           //function to decrement size of circular array dynamically
        int prev_size = getSize();
        if(prev_size<capacity/2){                         //if size is less than half of the capacity
            int[] new_array=new int[capacity/2];          //create new array of half of its size
            int index=front;                              //get front index
            int i=0;                                      //place an index to starting of new array (half the size)
            while(prev_size>=0){                          //while no of elements are present in the queue
                if(i==0)                                  //if index==0 place the first element
                    new_array[i]=queue[front++];
                else if(front==capacity){                 //front reached the end of array then place rear to start (circular array)      
                    front=0;
                    new_array[i]=queue[front++];
                }
                else
                    new_array[i]=queue[front++];         //else just add the element present in index of front
                prev_size--;                             //decrease the no of elements after putting to new array 
                i++;                                     //increase the index of i
            }
            front=0;                                     //assign front to 0
            rear=i-1;                                    //assign rear to index of last element present in new array(queue)
            capacity=capacity/2;                         //assign new capacity (half the size of prev)
            queue=new_array;                             //now queue will point to new array (or new queue)
        }
    }

    public void display() {                           //function to display queue
        int size = getSize();
        int index = front;

        while (size >= 0) {
            if (isEmpty())
                System.out.println("Empty queue");
            else if (index == capacity)
                index = 0;
            System.out.print(queue[index++] + "=>");
            size--;
        }
        System.out.println("  Capacity: "+capacity);

    }

}

出力：

--動的循環キュー--

1=> 容量: 2

1=>2=> 収容人数: 2

1=>2=>3=> 定員: 4

1=>2=>3=>4=> 定員: 4

4=>5=> 収容人数: 2