Saturday, May 16, 2009

A new method to distinguish between ring buffer full and empty

One design choice for ring buffer implementation is to distinguish
between full buffer and empty buffer. Traditional methods including
waste one entry for full (head + 1 == tail), or use
another flag for full. A new method is implemented as follow:

#define RING_LEN   16
#define RING_LIMIT (2 * RING_LEN - 1)

struct ring_entry
{
...
};

struct ring
{
int head;
int tail;
struct ring_entry entries[RING_LEN];
};

int ring_index(int n)
{
if (n > RING_LEN)
return n - RING_LEN;
else
return n;
};

int ring_get(struct ring *ring, struct ring_entry *entry)
{
/* empty */
if (ring->head == ring->tail)
return 0;

*entry = ring->entries[ring_index(ring->tail)];

ring->tail++;
if (ring->tail > RING_LIMIT)
ring->tail = 0;
return 1;
}

int ring_put(struct ring *ring, struct ring_entry *entry)
{
int ihead, itail;

ihead = ring_index(ring->head);
itail = ring_index(ring->tail);

/* full */
if (ihead == itail && ring->head != ring->tail)
return 0;

ring->entries[ihead] = *entry;

ring->head++;
if (ring->head > RING_LIMIT)
ring->head = 0;
return 1;
}

No comments: