¿Cómo implemento una lista circular (buffer de anillo) en C?
https://stackoverflow.com/questions/215557
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Cómo implemento una lista circular que sobrescribe la entrada más antigua cuando está llena?
Para un poco de historia, quiero usar una lista circular dentro de GWT; así que usar una biblioteca de terceros es no lo que quiero.
Solución
Una implementación muy simple, expresada en C. Implementa una cola FIFO de estilo de búfer circular. Podría hacerse más genérico al crear una estructura que contenga el tamaño de la cola, los datos de la cola y los índices de la cola (entrada y salida), que se enviarían con los datos para agregarlos o eliminarlos de la cola. Estas mismas rutinas podrían entonces manejar varias colas. También tenga en cuenta que esto permite colas de cualquier tamaño, aunque se pueden usar aceleraciones si usa potencias de 2 y personaliza el código aún más.
/* 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
}
Otros consejos
Usa una lista enlazada. Mantener punteros separados para la cabeza y la cola. Pop de la cabeza de la lista, empuje en la cola. Si lo quieres circular, asegúrate de que la nueva cola siempre apunte a la cabeza.
Puedo entender por qué es posible que desee implementar un FIFO utilizando una lista vinculada, pero ¿por qué hacer una lista circular?
Si quieres una lista circular de longitud fija. Puede utilizar una matriz (dinámica). Utilice dos variables para el mantenimiento de la casa. Uno para la posición del siguiente elemento, uno para contar el número de elementos.
Poner: poner elemento en lugar libre. Mover la posición (módulo de longitud). Agregue 1 a la cuenta a menos que la cuenta sea igual a la longitud de la lista. Obtener: solo si cuenta > 0. Mueva la posición hacia la izquierda (módulo de longitud). Disminuir el recuento.
Use una matriz y mantenga una variable P con la primera posición disponible.
Aumente P cada vez que agregue un nuevo elemento.
Para saber el índice equivalente de P en tu matriz, haz (P% n) donde n es el tamaño de tu matriz.
Estoy usando esto para mi microcontrolador. Para la simplicidad del código, un byte estará vacío. Aka size - 1 es la capacidad total en realidad.
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;
}
No creo que la cola sea la mejor manera de hacer un caché. ¡Quieres ser tu caché para ser realmente rápido! Y hacer un escaneo lineal de tu cola no es el camino a seguir, a menos que quieras que tu caché sea realmente pequeño o que tu memoria sea realmente limitada.
Suponiendo que no desea un caché muy pequeño o un caché lento, usar una Lista Vinculada con un Hash Map de valor a nodo en la lista enlazada es una buena manera de hacerlo. Siempre puede desalojar la cabeza, y cada vez que se accede a un elemento, puede eliminarlo y ponerlo en la cabecera de la lista. Para acceder puede obtenerlo directamente o verificar si está en el caché en O (1). El desalojo de un elemento también es O (1) y también lo es la actualización de la lista.
Para ver un ejemplo, mira LinkedHashMap en java.
http://docs.oracle.com/ javase / 6 / docs / api / java / util / LinkedHashMap.html
Esta es una forma elegante de crear cola circular que aumenta / disminuye dinámicamente usando java .
He comentado la mayor parte del código para facilitar & amp; comprensión rápida Espero que ayude :)
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:
--la cola circular dinámica--
1 = > Capacidad: 2
1 = > 2 = > Capacidad: 2
1 = > 2 = > 3 = > Capacidad: 4
1 = > 2 = > 3 = > 4 = > Capacidad: 4
4 = > 5 = > Capacidad: 2
