C에서 순환 리스트(ring buffer)를 어떻게 구현합니까?

C에서 순환 리스트(ring buffer)를 어떻게 구현합니까?

가장 오래된 항목이 가득 찼을 때 덮어쓰는 순환 목록을 구현하려면 어떻게 해야 합니까?

약간의 배경을 위해 GWT 내의 순환 리스트를 사용하고 싶기 때문에 서드파티 lib를 사용하는 것은 제가 원하는 것이 아닙니다.

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
}

연결된 목록을 사용합니다.머리와 꼬리에 대한 별도의 포인터를 유지합니다.목록의 맨 위에서 튀어나와 꼬리를 밀어 넣습니다.원형을 원하신다면 새 꼬리가 항상 머리를 가리켜야 합니다.

링크드 리스트를 사용하여 FIFO를 구현하려는 이유는 이해할 수 있지만 순환 리스트로 만드는 이유는 무엇입니까?

고정 길이 원형 리스트를 원하시는 경우.(동적) 배열을 사용할 수 있습니다.하우스키핑에는 두 개의 변수를 사용합니다.하나는 다음 요소의 위치에 사용하고, 하나는 요소의 개수를 세는 것입니다.

Put : 요소를 자유로운 곳에 놓습니다. 위치 이동(modulo length)카운트가 목록의 길이와 일치하지 않는 한 카운트에 1을 더합니다.Get: only if count > 0. 위치를 왼쪽(modulo length)으로 이동합니다.카운트를 줄입니다.

배열을 사용하고 변수 P를 처음 사용 가능한 위치에 유지합니다.

새 원소를 추가할 때마다 P를 늘립니다.

배열에서 P의 등가 인덱스를 알아보려면 (P % n)(여기서 n은 배열의 크기입니다.

마이크로컨트롤러에 사용하고 있습니다.코드 간소화를 위해 1바이트가 채워지지 않습니다.일명 size - 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; 
}

저는 대기열이 캐시를 만드는 가장 좋은 방법이라고 생각하지 않습니다.당신은 당신의 캐시가 되기를 원합니다.캐시가 매우 작거나 메모리가 매우 제한되지 않는 한 대기열을 선형 스캔하는 것은 바람직한 방법이 아닙니다.

매우 작은 캐시나 느린 캐시를 원하지 않는다고 가정할 때 링크된 목록에서 값의 해시 맵이 있는 링크된 목록을 링크된 목록의 노드에 사용하는 것이 좋습니다.항상 헤드를 제거할 수 있으며 요소에 액세스할 때마다 해당 헤드를 제거하여 목록 맨 앞에 배치할 수 있습니다.액세스의 경우 직접 가져오거나 O(1)의 캐시에 있는지 확인할 수 있습니다.요소를 제거하는 것도 O(1)이고 목록을 업데이트하는 것도 마찬가지입니다.

예를 들어 자바의 LinkedHashMap을 살펴봅니다.

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

여기 원형 버퍼(FIFO)를 위한 간단한 템플릿 솔루션이 있습니다.스토리지 공간 하나를 비워두기는 하지만, 이는 성능과 단순성에 대한 작은 불이익이라고 생각합니다.간단한 스트레스 테스트를 포함시켰습니다.

#include <iostream>
#include <string>

using namespace std;

class E: public std::exception {

    const char *_msg;
    E(){}; //no default constructor

public:

    explicit E(const char *msg) throw(): _msg(msg) {};
    const char * what() const throw() {return(_msg);};

};

const int min_size = 2;
const int max_size = 1000;

template<typename T>
class Fifo{

    int _head;
    int _tail;
    int _size;

    T* _storage;

public:

    explicit Fifo(int size = min_size);
    ~Fifo(){ delete [] _storage;};

    bool is_full() const{
        return(((_head+1)%_size) == _tail);
    };
    bool is_empty() const{
        return(_head == _tail);
    };

    void add_item(const T& item);
    const T& get_item();

};

template<typename T>
Fifo<T>::Fifo(int size): _size(size){
    
    if (size < min_size) throw E("Cannot create Fifo less than 2\n");

    _head = _tail = 0;

    try{

        _storage = new T[_size];
    }
    catch (std::bad_alloc &ba)
    {
        char e_string[500];
        sprintf(e_string, "Cannot allocate memory (%s)\n", ba.what());
        throw E(e_string);
    }

    printf("Constructing Fifo of size %d\n", _size);

}

template <typename T>
void Fifo<T>::add_item(const T& item)
{
    if (this->is_full()) throw E("Fifo is full.\n");

    _storage[_head] = item;

    _head = (_head + 1)%_size;
}

template <typename T>
const T& Fifo<T>::get_item()
{
    if (this->is_empty()) throw E("Fifo is empty.\n");

    int temp = _tail; //save the current tail

    _tail = (_tail+1)%_size; //update tail

    return(_storage[temp]);
}

int main()
{
    Fifo<int> my_fifo(3);

    for (int i = 1, item; i < 50; i++)
    {
        my_fifo.add_item(i);
        my_fifo.add_item(i*10);
        item = my_fifo.get_item();
        printf("Item: %d\n", item);
        item = my_fifo.get_item();
        printf("Item: %d\n", item);
    }


    return 0;
}

자바를 사용하여 동적으로 증가/감소하는 순환 큐를 만드는 우아한 방법이 있습니다.

코드의 대부분을 쉽고 빠르게 이해할 수 있도록 코멘트를 달았습니다.도움이 되길 바랍니다 :)

    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

언급URL : https://stackoverflow.com/questions/215557/how-do-i-implement-a-circular-list-ring-buffer-in-c