Как установить размер круговой очереди

Question

Я пытаюсь реализовать общий кольцевой буфер (очередь) в C. Вот мой код до сих пор:

#include <stdio.h> 
#include <stdlib.h> 
#include <sys/queue.h> 

CIRCLEQ_HEAD(circleq, entry) head; 
struct circleq *headp;    /* Circular queue head. */ 
struct entry { 
    CIRCLEQ_ENTRY(entry) entries; /* Circular queue. */ 
    int number; 
}; 

int main() 
{ 
    CIRCLEQ_INIT(&head); 

    // Add some numbers to the queue 
    int i; 
    for (i = 0; i < 10; i++) { 
    struct entry* n = malloc(sizeof(struct entry)); 
    n->number = i; 
    CIRCLEQ_INSERT_HEAD(&head, n, entries); 
    printf("Added %d to the queue\n", n->number); 
    } 

    // Remove a number from the queue 
    struct entry *n; 
    n = CIRCLEQ_FIRST(&head); 
    CIRCLEQ_REMOVE(&head, head.cqh_first, entries); 
    printf("Removed %d from the queue\n", n->number); 

    return 0; 
} 

Который производит следующий вывод:

Added 0 to the queue 
Added 1 to the queue 
Added 2 to the queue 
Added 3 to the queue 
Added 4 to the queue 
Added 5 to the queue 
Added 6 to the queue 
Added 7 to the queue 
Added 8 to the queue 
Added 9 to the queue 
Removed 9 from the queue 

Я не очень опытный с C, и мои вопросы:

1. Как установить ограничение на очереди, так, например, ОНЛ y 5 номеров может поместиться в буфер за раз? Если после этого будет добавлен другой элемент, то после него будет добавлен , я должен его обнаружить и сделать что-то об этом (проигнорируйте его, подождите, выйдите из программы и т. Д.).

2. Кажется, мой код удаляется последний элемент из буфера - как я могу сделать это удалить элементы из хвоста (номер 0 вместо 9, в моем примере)?

Я прочитал http://linux.die.net/man/3/queue, но это не кажется, ясно, как я могу выполнить вышеуказанные две вещи.

Answer 1

1. Если посмотреть на описание circular-buffer, один из главных преимуществ такого буфера является то, что он использует одно фиксированное распределение, в то время как ваш в основном только циркулярно связанный список. Фиксированный размер, используемый при создании, определяет предел количества элементов, которые может удерживать кольцевой буфер.

2. Если у вас есть правильно реализованный круговой буфер, удаление элемента связано с простое продвижение указателя на хвост, при необходимости завертывание на передний план.

В качестве примера структура, представляющая собой кольцевой буфер может выглядеть следующим образом:

struct circleq 
{ 
    int* buf; 
    int head; 
    int tail; 
    int size; 
}; 

void init(struct circleq* q, int size) 
{ 
    q->buf = malloc(sizeof(int) * size); 
    q->head = 0; 
    q->tail = size - 1; 
    q->size = size; 
} 

void insert(struct circleq* q, int val) 
{ 
    if(q->head == q->tail) { } // queue full, error 
    else 
    { 
     q->buf[q->head] = val; 
     q->head = (q->head + 1) % q->size; 
    } 
} 

int remove(struct circleq* q) 
{ 
    if((q->tail + 1) % q->size == q->head) { return 0; } // queue empty, error 
    else 
    { 
     int val = q->buf[q->tail]; 
     q->tail = (q->tail + 1) % q->size; 
     return val; 
    } 
} 

void destroy(struct circleq* q) 
{ 
    free(q->buf); 
}