How do you Design a Circular FIFO Buffer (Queue) in C?

Circular_Buffer_Animation

I was recently being asked by this question: How do you Design a Circular FIFO (First-In First-out) Buffer (Queue) in C? You need to implement two methods: fifoRead and fifoWrite, which reads or writes a byte to the buffer respectively.

The requirements are:

• C Implementation Only.
• Circular Buffer
• First-In-First-Out
• fifoRead will read a byte from the buffer, if the buffer is empty, it should return a EMPTY error code.
• fifoWrite will write a byte to the buffer, if the buffer is full, it should return a FULL error code.
• The size of the buffer is fixed (not changing dynamically runtime).

It is fixed size so the best data structure is the static array that we can use to represent the buffer.

1
2
3
4
5

#define BUFFER_SIZE 100
#define ERROR_EMPTY 0
#define ERROR_FULL 0xFF
 
char buffer[BUFFER_SIZE];

#define BUFFER_SIZE 100
#define ERROR_EMPTY 0
#define ERROR_FULL 0xFF

char buffer[BUFFER_SIZE];

We can then have two index-pointers head and tail pointing to the beginning and the end of the buffer, default to zeros.

1

int head = 0, tail = 0;

int head = 0, tail = 0;

When a byte is to insert into the buffer, we move the head and on the other hand, when a byte is about to be read from the buffer we move the tail.

If we all move the head and tail in clock-wise direction (moving to the right), we also need to rewind the pointers when they reach the end of the array i.e. head = (head + 1) % BUFFER_SIZE and tail = (tail + 1) % BUFFER_SIZE

We can use a counter variable to record the number of stored-bytes in the buffer. Therefore, the fifoRead and fifoWrite can be implemented as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int count = 0; 
 
// reads a byte from the buffer and return ERROR_EMPTY if buffer empty
char fifoRead() {
   if (0 == count) return ERROR_EMPTY;
   count --;
   tail = (tail + 1) % BUFFER_SIZE;
   return buffer[tail];
}
 
// writes a byte to the buffer if not ERROR_FULL
char fifoWrite(chat val) {
   if (BUFFER_SIZE == count) return ERROR_FULL;
   count ++;
   head = (head + 1) % BUFFER_SIZE;
   return buffer[head] = val;
}

int count = 0; 

// reads a byte from the buffer and return ERROR_EMPTY if buffer empty
char fifoRead() {
   if (0 == count) return ERROR_EMPTY;
   count --;
   tail = (tail + 1) % BUFFER_SIZE;
   return buffer[tail];
}

// writes a byte to the buffer if not ERROR_FULL
char fifoWrite(chat val) {
   if (BUFFER_SIZE == count) return ERROR_FULL;
   count ++;
   head = (head + 1) % BUFFER_SIZE;
   return buffer[head] = val;
}

We don’t like global variables in this case counter. When you do counter — or counter ++, what computer does is to copy the value from memory counter to register, increment or decrement the register, and copy the value from register back to the memory. In case of hardware interrupts (similar to multithreading), the value of counter may be incorrectly updated.

So, if we get rid of the counter, how do we check if the buffer is empty or full? The answer is in the head and tail itself.

circular-fifo-buffer

When the buffer if empty, the head == tail is true. And when the buffer is about to be full, the head + 1 == tail is true.

1
2
3
4
5
6
7
8
9
10
11
12
13

// reads a byte from the buffer and return ERROR_EMPTY if buffer empty
char fifoRead() {
   if (head == tail) return ERROR_EMPTY;
   tail = (tail + 1) % BUFFER_SIZE;
   return buffer[tail];
}
 
// writes a byte to the buffer if not ERROR_FULL
char fifoWrite(chat val) {
   if (head + 1 == tail) return ERROR_FULL;
   head = (head + 1) % BUFFER_SIZE;
   return buffer[head] = val;
}

// reads a byte from the buffer and return ERROR_EMPTY if buffer empty
char fifoRead() {
   if (head == tail) return ERROR_EMPTY;
   tail = (tail + 1) % BUFFER_SIZE;
   return buffer[tail];
}

// writes a byte to the buffer if not ERROR_FULL
char fifoWrite(chat val) {
   if (head + 1 == tail) return ERROR_FULL;
   head = (head + 1) % BUFFER_SIZE;
   return buffer[head] = val;
}

In this case, we can only store BUFFER_SIZE – 1 elements in the buffer because we have to distinguish between BUFFER emtpy and BUFFER full.

–EOF (The Ultimate Computing & Technology Blog) —