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.
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) —
loading...
Last Post: How To Determine The Best Antivirus For Your Device?
Next Post: Coding Exercise - How to Merge Two Sorted Array?
This doesn’t even assign a value (variable “val”) into the fifo! This is worthless.
Typo fixed. Thanks.!
There’s half a dozen bugs in this easily. Store the return value before incrementing so you have it for the return. Check the bounds on the write before comparing head and tail. I would give this an ‘F’. They didn’t even try the code, it clearly doesn’t work.
There are two ways, one is to use the counter, the other is to compare with the head and tail.
Not a circular buffer, keeps going on forever, doesn’t rollover. Use a % operator or an if statement . What about initialization? This doesn’t work.
Yes, it uses a “%” operator to go around, don’t you read the code?
code is riddled with errors
LOL, it is pusdo code.