Circular Queue in C for an embedded project

Question

I wrote a simple circular queue. (in order to store characters because of the fact, that I am using UART through the DMA and sometimes my printf's override each other) I am looking for some review, though my testfile was successful I have the feeling I've overseen something and the queue might be buggy at some point. I appreciate any kind of critics, ideas or improvements

Header File:

#ifndef __QUEUEH
#define __QUEUEH
typedef struct queue {
 unsigned int head;
 unsigned int tail;
 unsigned char* buf;
 unsigned int bufSize;
 unsigned int freeSpace;
 unsigned int occuSpace;
 unsigned char initialized;
} queue_t;
extern int queue_init(queue_t* q, unsigned char* buf, unsigned int bufSize);
extern int enqueue(queue_t* q, unsigned char* element, unsigned int size);
extern int dequeue(queue_t* q, unsigned char* str, int strMaxSize);
// change to static
extern int printQueue(queue_t* q);
#endif

C-File:

#include "queue.h"
#if !defined bool
typedef unsigned char bool;
#endif
extern int queue_init(queue_t* q, unsigned char* buf, unsigned int bufSize) {
 q->head = -1;
 q->tail = 0;
 q->buf = buf;
 q->bufSize = bufSize;
 q->freeSpace = bufSize;
 q->occuSpace = 0;
 q->initialized = 1;
 return 0;
}
static inline bool moveTail(queue_t* q) {
 q->occuSpace = q->occuSpace - 2 - (q->buf)[q->tail];
 q->freeSpace = q->freeSpace + 2 + (q->buf)[q->tail];
 q->tail = (q->tail + (q->buf)[q->tail]+2) % (q->bufSize);
 return 0;
}
static inline bool enoughSpaceAvailable(queue_t* q, unsigned int size) {
 if(q->freeSpace < size+2)
 return 0;
 return 1;
}
extern int enqueue(queue_t* q, unsigned char* element, unsigned int size) {
 if(size==0)
 return -5;
 else if(size>q->bufSize-2)
 return -8;
 while(!enoughSpaceAvailable(q,size))
 moveTail(q);
 q->occuSpace = q->occuSpace + 2 + size;
 q->freeSpace = q->freeSpace - 2 - size;
 q->head = (q->head+1)%(q->bufSize);
 (q->buf)[q->head] = size;
 for(int i = 0; i<size; i++) {
 q->head = (q->head+1)%(q->bufSize);
 (q->buf)[q->head] = element[i];
 }
 q->head = (q->head+1)%(q->bufSize);
 (q->buf)[q->head] = size;
 return 0;
}
extern int dequeue(queue_t* q, unsigned char* str, int strMaxSize) {
 int len = q->buf[q->tail];
 if(q->freeSpace == q->bufSize) return -6; else if(strMaxSize<len) return -7;
 for(int j=0; j<len; j++) {
 str[j] = q->buf[(q->tail+1+j)%(q->bufSize)];
 }
 moveTail(q);
 return 0;
}

• chux: Please explain the comment "change to static".
• Town Tattle: I put it there to indicate, that the print function wasnt meant to be an extern function

Answer 1

Redundant bytes

What's confusing about your implementation is that you are using two extra bytes for each element enqueued, but those bytes are redundant. You are adding a size byte both before and after each element, but only the "before" byte is ever used. You should remove the "after" byte because it serves no purpose.

Size byte is not large enough

You only reserve room for a single byte to indicate the size of the element. However, your enqueue() function takes unsigned int size as its argument. Therefore, if size is greater than 255, your program will encode the incorrect value in the size byte and things will fail after that. Either you should leave room for sizeof(unsigned int) bytes to encode the size, or you should limit the size argument to an unsigned char if you expect to only enqueue data smaller than 256 bytes.

Miscellaneous

• The field occuSpace is set but never used. You should remove that field, because you can always compute the value as bufSize - freeSpace anyways.

• The field initialized is set but never used. It should either be removed, or you should check it in all your functions and return an error if the queue is not initialized.

• Instead of returning -5, -8, and -7 as error codes, you should define some error codes in your header and return them instead of hardcoded numbers.

• Some functions such as queue_init() and moveTail() can't fail and always return 0. You should either make those functions return void since they can't fail, or modify them to check for error conditions and possibly return an error code. For example, in queue_init(), you could check for these errors:

  • q == NULL
  • buf == NULL
  • bufSize == 0

• Instead of:

#if !defined bool
typedef unsigned char bool;
#endif

just do

#include <stdbool.h>

You should also use false and true instead of 0 and 1, for the functions that return bool.

• Town Tattle: In order to confirm: The size byte after each element was useless. I added a second size byte at the beginning, so now I can add strings with the maximum length of two bytes. Occupied space was useless. And your other recommendations I implemented too.
• JS1: @OliverAl-Hassani yes that is all correct.

Answer 2

Functionality unclear

Post discusses "... circular queue. (in order to store characters ...".

After digging deeply into code I now realize the goal is not to enqueue a character and then a character and so on. Instead the goal is to enqueue a group of characters, then another group and so on.

This is not clear from the the post and importantly, it is not clear from the .h file.

Documentation

The .h file, as a public interface deserves as least a little documentation/comment per function.

Nonuniform name-space

__QUEUEH, queue, queue_init, enqueue, dequeue, printQueue would benefit with a more common naming convention to clearly show that they belong together.

Consider QUEUE_H, queue, queue_init, queue_set, queue_get, queue_print

queue_t

Information hiding: The members of queue_t do not need to be in the .h file. The below is sufficient. If external code needs to read any of these members, I recommend a function to do so.

typedef struct queue queue_t;

Put the full struct queue definition in the .c file.

.initialized is a good candidate for bool.

// unsigned char initialized;
bool initialized;

Unnecessary item in .h

As a static function, printQueue does not belong in the .h file. Remove it.

---

Avoid standard library collisions

The below conflicts with bool from stdbool.h. Do not re-invent the standard boolean type.

// #if !defined bool
// typedef unsigned char bool;
// #endif
#include <stdbool.h>

queue_init()

Why set .head, an unsigned type, to a negative value? Set to a unsigned value.

// q->head = -1;
q->head = -1u;

moveTail()

The role of magic number 2 is unclear here and in many of the functions. Explain the 2.

Unexpected strMaxSize

How does reading the data in the queue relate to the length of anything?

int len = q->buf[q->tail];

The role of strMaxSize in dequeue() is unclear.

Hmmmmm

After more review it looks like the first character in a group of characters is the group's length.

enoughSpaceAvailable()

Avoid overflow: size+2 can overflow - this code has no control over the value of size. Consider a more robust test.

// if(q->freeSpace < size+2) return 0;
//return 1;
return q->freeSpace > size && q->freeSpace - size >= 2;

const

Many functions would benefit with a const queue_t *

// enoughSpaceAvailable(queue_t* q, unsigned int size)
enoughSpaceAvailable(const queue_t* q, unsigned int size)

3 to do the job of 2

Unclear why code uses .bufSize, .freeSpace, .occuSpace when only 2 are needed. I'd expect .bufSize, .occuSpace are sufficient here.

---

Overall

Code lacks documentation to indicate the overall coding goals. Without that, there is too much to discover.

I still do not know how to use best these calls. Will enqueue(q, "", 0); cause havoc? How to test is the queue is empty? What are all the error codes? Why are errors negative? What does a positive response mean?

To me, it is the un-posted testfile contains too much information there and not enough here.

This code deserves an update and then a following review.

---

Sample alternate aqueue.h.
I avoided "queue" as too generic and used "aqueue".

/*
 * aqueue: queue of groups of binary data
 */
#ifndef AQUEUE_H
#define AQUEUE_H
typedef struct aqueue aqueue_t;
// All functions that return `int` return 0 on success.
/*
 * Initialize the queue with the buffer to use and its size.
 * Size [4..UINT_MAX]
 * Return TBD with invalid parameter values.
 */
int aqueue_init(aqueue_t* q, unsigned char* buf, unsigned bufSize);
/*
 * Insert a copy of what `data` points to.
 * Return TBD with insufficient space
 */
int queue_set(aqueue_t* q, const unsigned char* data, unsigned dataSize);
/*
 * Extract entry from the queue.
 * Return TBD when attempted with empty queue.
 * Return TBD when dataSize is too small.
 */
int aqueue_get(aqueue_t* q, unsigned char *data, unsigned dataSize);
/*
 * Queue empty?
 */
_Bool aqueue_empty(const aqueue_t* q);
/*
 * Get data without removing from the queue (Peek)
 * Return TBD when attempted with empty queue.
 * Return TBD when dataSize is too small.
 */
int aqueue_top(const aqueue_t* q, unsigned char* data, unsigned dataSize);
#endif

• chux: The calling code likely needs to know the size of queue_t thwarting my information hiding suggestion. If so, leave the full declaration of queue_t in the.h file.
• chux: @Oliver Al-Hassani I see the need for queue_t within the header file as a design weakness. It implies that the unposted calling code (main()) is doing things it should not. A better queue_... would hide the inner details from the calling code. Think of FILE as in fopen(), fgetc(), fprintf(), fclose(). What do we know of its size, or members - very little. That is how your queue_... should be too.
• chux: @OliverAl-Hassani The member of FILE though are not needed to use the standard FILE functions. There is no need for FILE f, just FILE *f. Any access to FILE members is a matter of performance (in-lining code) vs. a function call. Code as you like, yet I find abstracted helper code, like this queue could be, to have more long term value when coded and used in a manner that separates the members from the caller.
• chux: @OliverAl-Hassani Consider the trade-off of "it's getting more complicated than pragmatic". It is usually more valuable and pragmatic to minimize the complication of the calling code, even if that makes this queue code more complex. There are various ways to handle the difficultly in memory management, but in the end, the idea is to make it easy from the caller-point-of-view - regardless of which way you choose to manage memory. Perhaps knowing more why your application needs to avoid malloc() would help - yet that is getting beyond the scope of this answer.
• Lundin: Excellent review. Regarding the bool remark, the reason might be to allow C90 compatibility, as often required because of dusty old embedded system compilers. The correct way to do it would however rather be #ifndef __STDC_VERSION__ typedef unsigned char bool; #define false 0 #define true 1 #else #include <stdbool.h> #endif. But then of course this doesn't give true booleans. Given bool b = 2;, C90 fake boolean will get value 2, whereas standard C boolean will get value 1.