Wie implementiere ich eine Kreisliste (Ringpuffer) in C?
https://stackoverflow.com/questions/215557
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Wie implementiere ich eine Kreisliste, die den ältesten Eintrag überschreibt, wenn er voll ist?
Für ein wenig Hintergrund möchte ich in GWT eine zirkulare Liste verwenden; so eine lib 3rd-Party mit ist nicht , was ich will.
Lösung
Eine sehr einfache Implementierung, ausgedrückt in C. Implementiert einen kreisförmigen FIFO-Warteschlangenpuffer-Stil. Könnte eine Struktur, die durch die Schaffung der Warteschlangengröße enthält, Warteschlangendaten und Warteschlangen Indizes (in der und aus) gemacht generisch sein, die mit den Daten übergeben werden, würden von der Warteschlange hinzuzufügen oder zu entfernen. Diese gleichen Routinen könnten dann mehrere Warteschlangen umgehen. Beachten Sie auch, dass diese Warteschlangen jeder Größe ermöglicht, obwohl speedups verwendet werden können, wenn Sie verwenden Potenzen von 2 und fertigen Sie den Code weiter.
/* 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
}
Andere Tipps
Verwenden Sie eine verknüpfte Liste. Pflegen separate Zeiger für den Kopf und Schwanz. Pop von der Spitze der Liste, drücken Sie auf den Schwanz. Wenn Sie es kreisförmig wollen, nur sicherstellen, dass die neuen Schwanz immer auf den Kopf.
ich kann verstehen, warum Sie ein FIFO mit einer verknüpften Liste implementieren möchten, aber warum es eine kreisförmige Liste machen?
Wenn Sie eine feste Länge zirkularen Liste. Sie können ein (dynamisches) Array. Verwenden Sie zwei Variablen für houskeeping. Ein für die Position des nächsten Elements, eine die Anzahl der Elemente zu zählen.
Setzen: put Element auf freien Platz. bewegen, um die Position (Modulo-Länge). 1 zu der Zählung, es sei denn die Zählung lengtht der Liste entspricht. Erhalten Sie: Nur wenn count> 0. bewegen, um die Position nach links (Modulo-Länge). Dekrementiert die Zählung.
ein Feld verwenden und eine Variable P mit der ersten verfügbaren Position zu halten.
Erhöhung P jedes Mal ein neues Element hinzuzufügen.
Zur Ermittlung des Äquivalents Index von P in Ihrem Array wissen tun (P% n), wobei n die Größe des Arrays ist.
Ich verwende für meine Mikrocontroller. Für Code Einfachheit wird ein Byte ungefüllt sein. Aka Größe -. 1 ist die volle Kapazität tatsächlich
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;
}
Ich glaube nicht Warteschlange der beste Weg ist, einen Cache zu machen. Sie wollen Ihr Cache, um wirklich schnell zu sein! Und eine lineare Scan Ihrer Warteschlange tut, ist nicht der Weg zu gehen, wenn Sie den Cache wirklich will, klein sein oder Ihr Gedächtnis ist wirklich begrenzt.
Unter der Annahme, dass Sie nicht wollen, einen sehr kleinen Cache oder einen langsamen Cache, eine verkettete Liste mit einer Hash-Karte von Wert mit in der Liste Knoten ist ein guter Weg zu gehen. Sie können immer den Kopf vertreiben, und immer dann, wenn ein Element zugegriffen wird, können Sie es entfernen und es in der Spitze der Liste setzen. Für den Zugriff können Sie es direkt erhalten oder überprüfen, ob es in dem Cache in O (1). ein Element evicting ist auch O (1) und so die Liste aktualisiert.
Ein Beispiel sehen Sie LinkedHashMap in Java.
http://docs.oracle.com/ JavaSE / 6 / docs / api / java / util / LinkedHashMap.html
Hier ist eine elegante Art und Weise zu schaffen dynamisch Erhöhungs- / Verringerungs zirkuläre Warteschlange mit java .
Ich habe die meisten Teil des Codes für die einfache und schnelle Verständnis kommentiert. Hoffe, es hilft:)
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);
}
}
Ausgang:
- dynamic zirkuläre Warteschlange -
1 => Kapazität: 2
1 => 2 => Kapazität: 2
1 => 2 => 3 => Kapazität: 4
1 => 2 => 3 => 4 => Kapazität: 4
4 => 5 => Kapazität: 2
