Come posso implementare un elenco circolare (ring buffer) in C?
https://stackoverflow.com/questions/215557
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Come posso implementare un elenco circolare che sovrascrive la voce più vecchia quando è piena?
Per un piccolo background, voglio usare un elenco circolare all'interno di GWT; quindi usare una lib di terze parti non è non quello che voglio.
Soluzione
Un'implementazione molto semplice, espressa in C. Implementa una coda FIFO in stile buffer circolare. Potrebbe essere reso più generico creando una struttura contenente le dimensioni della coda, i dati della coda e gli indici della coda (dentro e fuori), che verrebbero trasferiti con i dati da aggiungere o rimuovere dalla coda. Queste stesse routine potrebbero quindi gestire diverse code. Si noti inoltre che ciò consente code di qualsiasi dimensione, sebbene le accelerazioni possano essere utilizzate se si utilizzano potenze di 2 e si personalizza ulteriormente il codice.
/* 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
}
Altri suggerimenti
Utilizza un elenco collegato. Mantenere puntatori separati per la testa e la coda. Pop dalla testa della lista, spingere sulla coda. Se lo vuoi circolare, assicurati solo che la nuova coda punti sempre verso la testa.
Posso capire perché potresti voler implementare un FIFO usando un elenco collegato, ma perché trasformarlo in un elenco circolare?
Se si desidera un elenco circolare di lunghezza fissa. È possibile utilizzare un array (dinamico). Utilizzare due variabili per la pulizia. Uno per la posizione dell'elemento successivo, uno per contare il numero di elementi.
Metti: metti l'elemento in un posto libero. sposta la posizione (lunghezza del modulo). Aggiungi 1 al conteggio a meno che il conteggio sia uguale alla lunghezza dell'elenco. Ottieni: solo se conta > 0. spostare la posizione a sinistra (lunghezza del modulo). Diminuisci il conteggio.
Usa un array e mantieni una variabile P con la prima posizione disponibile.
Aumenta P ogni volta che aggiungi un nuovo elemento.
Per conoscere l'indice equivalente di P nel tuo array (P% n) dove n è la dimensione del tuo array.
Lo sto usando per il mio microcontrollore. Per semplicità di codice, un byte non sarà riempito. Aka size - 1 è la piena capacità in realtà.
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;
}
Non credo che la coda sia il modo migliore per creare una cache. Vuoi essere la tua cache per essere davvero veloce! E fare una scansione lineare della coda non è la strada da percorrere a meno che tu non voglia che la tua cache sia davvero piccola o la tua memoria sia davvero limitata.
Supponendo che non si desideri una cache molto piccola o una cache lenta, utilizzare un Elenco collegato con una Hash Map di valore da nodo nell'elenco collegato è un buon modo di procedere. Puoi sempre sfrattare la testa e ogni volta che accedi a un elemento, puoi rimuoverlo e metterlo in testa alla lista. Per l'accesso è possibile ottenerlo direttamente o verificare se si trova nella cache in O (1). Lo sfratto di un elemento è anche O (1), così come l'aggiornamento dell'elenco.
Per un esempio, guarda LinkedHashMap in java.
http://docs.oracle.com/ JavaSE / 6 / docs / api / java / util / LinkedHashMap.html
Ecco un modo elegante per creare coda circolare in aumento / diminuzione dinamica utilizzando java .
Ho commentato la maggior parte del codice per easy & amp; comprensione veloce. Spero che sia d'aiuto :)
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);
}
}
Output:
- coda circolare dinamica--
1 = > Capacità: 2
1 = > 2 = > Capacità: 2
1 = > 2 = > 3 = > Capacità: 4
1 = > 2 = > 3 = > 4 = > Capacità: 4
4 = > 5 = > Capacità: 2
