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

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.

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.

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.