Implementing a generic Queue in C

Question

I wrote a generic Queue that could with work any data type you give it. The Queue can do any the basic operations that you would expect a Queue can do such as enqueue, dequeue, peek and so on.

I would like you to critique me on:

• My general style
• My ability to properly deallocate memory so that there is no memory leaks
• Properly handling memory allocation failure
• Anything else that you would like to add

Queue.h

#ifndef QUEUE_H_INCLUDED
#define QUEUE_H_INCLUDED
typedef struct Node
{
 void *data;
 struct Node *next;
}node;
typedef struct QueueList
{
 int sizeOfQueue;
 size_t memSize;
 node *head;
 node *tail;
}Queue;
void queueInit(Queue *q, size_t memSize);
int enqueue(Queue *, const void *);
void dequeue(Queue *, void *);
void queuePeek(Queue *, void *);
void clearQueue(Queue *);
int getQueueSize(Queue *);
#endif /* QUEUE_H_INCLUDED */

Queue.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Queue.h"
void queueInit(Queue *q, size_t memSize)
{
 q->sizeOfQueue = 0;
 q->memSize = memSize;
 q->head = q->tail = NULL;
}
int enqueue(Queue *q, const void *data)
{
 node *newNode = (node *)malloc(sizeof(node));
 if(newNode == NULL)
 {
 return -1;
 }
 newNode->data = malloc(q->memSize);
 if(newNode->data == NULL)
 {
 free(newNode);
 return -1;
 }
 newNode->next = NULL;
 memcpy(newNode->data, data, q->memSize);
 if(q->sizeOfQueue == 0)
 {
 q->head = q->tail = newNode;
 }
 else
 {
 q->tail->next = newNode;
 q->tail = newNode;
 }
 q->sizeOfQueue++;
 return 0;
}
void dequeue(Queue *q, void *data)
{
 if(q->sizeOfQueue > 0)
 {
 node *temp = q->head;
 memcpy(data, temp->data, q->memSize);
 if(q->sizeOfQueue > 1)
 {
 q->head = q->head->next;
 }
 else
 {
 q->head = NULL;
 q->tail = NULL;
 }
 q->sizeOfQueue--;
 free(temp->data);
 free(temp);
 }
}
void queuePeek(Queue *q, void *data)
{
 if(q->sizeOfQueue > 0)
 {
 node *temp = q->head;
 memcpy(data, temp->data, q->memSize);
 }
}
void clearQueue(Queue *q)
{
 node *temp;
 while(q->sizeOfQueue > 0)
 {
 temp = q->head;
 q->head = temp->next;
 free(temp->data);
 free(temp);
 q->sizeOfQueue--;
 }
 q->head = q->tail = NULL;
}
int getQueueSize(Queue *q)
{
 return q->sizeOfQueue;
}

TestQueue.c

#include <stdio.h>
#include <stdlib.h>
#include "Queue.h"
int main()
{
 int val;
 Queue q;
 queueInit(&q, sizeof(int));
 for(val = 0; val < 10; val++)
 {
 enqueue(&q, &val);
 printf("The value %d has been enqueued.\n", val + 1);
 }
 printf("\n");
 queuePeek(&q, &val);
 printf("The value that is at the front of the queue is %d\n\n", val + 1);
 while(getQueueSize(&q) > 0)
 {
 dequeue(&q, &val);
 printf("%d has been dequeued.\n", val + 1);
 }
 return 0;
}

Output

enter image description here

• 200_success: I have rolled back Rev 2 → 1, as it just adds confusion to have a second version of the code in the question for no good reason. You can either make this a proper comparative-review question (only if you can do so without making any existing answers look silly) or post a follow-up question.
• fernando.reyes: Why not use dequeue on clearQueue until empty?
• Luis Averhoff: @fernando.reyes So then do something like this int val while(q->sizeOfQueue > 0){dequeue(q, &val)} q->head = q->tail = NULL;This of course would be in the clearQueue function.
• fernando.reyes: @LuisAverhoff Your dequeue will even make head and tail null, that is already taken care off. And will avoid duplicated code for when you need to make a change in logic on your code
• Luis Averhoff: @fernando.reyes oops yes your right that in the dequeue function function I'm already making making head and tail equal to null if there is one element in the queue.

Answer 1

1. Pattern-less function names. For Queue.h, rather see function named obviously make sense together like Queue_Init(), Queue_GetSize() than queueInit(), getQueueSize(), etc.

2. Comments with # preprocessing may not be portable

   // #endif /* QUEUE_H_INCLUDED */
   #endif
   

3. There is no need for a head and tail. Alternative, only store tail and have the tail point to the head of the list. End of list detected when p->next == tail->next. This makes your head node one field smaller. Important if code uses lots of queues.

4. Unclear why code uses int for the queue size type. A signed type is not needed (could use unsigned) and on a system where size_t could be much wider than int, a queue size like size_t is more prudent. Robust code would check for a queue exceed the max value of size in enqueue().

5. Good use of size_t for memSize. Good error checking for malloc(). Good to have test case. IMO, a commented sample usage in the *.h file is nice. ; the *.h being the public interface to your good code.

6. Pedantic: Robust would check for memSize==0 in queueInit() as that negates the correctness of the malloc() checks which should be if(newNode->data == NULL && q->memSize > 0).

7. A little documentation goes a long way. suggest a line or two of comment preceding each function declaration in Queue.h.

8. Functions like queuePeek(Queue *q, void *data) that do not alter *q should be declared queuePeek(const Queue *q, void *data). This self documents the unchanging nature of q in the function to users and allows some optimizations a compiler may not otherwise employ. It is a check on the implementation of the function too.

9. For completeness, suggest q->memSize = 0 in clearQueue().

10. Change #include order. Put "Queue.h" first as a check that Queue.h does not depend on the 3 <*.h> include files - unless that .h file is coded in Queue.h.

    #include "Queue.h"
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    // #include "Queue.h"
    

11. Indicate failure. If void dequeue(Queue *q, void *data) does not have anything in the queue to copy to data, there is no indication of that here. Perhaps return true/false indicating success. Same for queuePeek().

12. For debugging, zero filling memory before free() I have found useful. Errant code tends to fail faster with a 0 pointer/data than with its original data still potentially intact. Faster failing code is easier to debug. YMMV.

13. Opinion: Storing the queue size is of dubious value, unless of course that is the reason for the queue type - one with a quick size report. Alternative, drop the size field and calculate when needed. More often, I have found the need for bool Queue_IsEmpty(const Queue *q) sufficient than needing a quick size and prefer to drop the ever present size field.

• chux: See this comment for an idea to avoid the second level allocation when the size of data will fit in a pointer.
• Luis Averhoff: In regards to number 10, I have to use Queue.h after the stdlib.h else it wont recognize any variable in my header file that have the type size_t. Could you elaborate on 12 with an example? What do you mean by zero filling memory before free? Like setting the pointer to NULL before calling free?
• chux: @Luis Averhoff The .h file should contain #include <stdlib.h>. Your commented problem is precisely why #include "Queue.h" should be first (#10) as it detected that - but IMO, your fix was wrong.
• chux: @Luis Averhoff Per #12, recommending memset(newNode, 0, sizeof *NewNode); free(newNode); to zero the referenced data pointed to by newNode before free().

Answer 2

Node seems quite a common struct name to me. And you don't use it outside of the Queue struct. So I think you could define it in the .c file to avoid using up that precious type name.

• Luis Averhoff: Good point. it makes sense to made the node structure private to the queue.c file.

Answer 3

#include <stdbool.h>

I would include the above header file and return true/false from enqueue/dequeue depending whether the operation was successful or not.

Don't copy data

Also, I would not copy the actual objects to the queue nodes. You can simply store the void* pointers in the queue nodes. This will improve performance of your software.

Minor

You could remove #include <stdio.h> from the .c file since console I/O is not actually used.

Otherwise, your code and API seem plausible to me.

• Luis Averhoff: So for queuePeek, I can have it return a void * like this return q->head->data; . For enqueue, I can do newNode->data = data; correct? It seems for dequeue that I'm going to have use memcpy.
• coderodde: @LuisAverhoff I would rather stick to your pattern of returning a boolean as an indicator of the success of the called operation. If you, say, peek from an empty queue, don't modify anything pointed by *data, but return false. If not empty, return true and set data appropriately.
• chux: Disagree with "Don't copy data". That idea makes sense if the data to be queued is always a pointer. Yet OP's goal is "work any data type you give it". Example. If my data was type long double, trying to copy that or its address into a void * would fail.
• chux: Pass an long double* and only storing the pointer as you suggest obliges the calling code to allocate space and goes against OP's goal of "work any data type you give it". Pedantically your idea does not handle pointer to functions, which may not fit in void* - unless calling code allocates for that too. OP's interacts with calling code by passing a reference to the data, not the data itself (which may be of any size). OTOH I have, worked with libraries had the best/worst of both, when memSize <= sizeof(void*), no need to allocate, just store the value in a unionized void*.
• chux: @Luis Averhoff Re: "I also dont think I need to do memcpy in enqueue either." Consider { long double x = 1/7.0; enqueue(q, &x); } .... { long double y; dequeue(q, ....); How to call dequeue() to put a value in y? without a memcpy() in enqueue()? The address for x is long since invalid.