10
\$\begingroup\$

Simple lightweight queue implementation using data size registration and singly linked lists as the underlying type

Update #2

/*
    Author: Jared Thomas
    Date:   Tuesday, August 2, 2022
    
    Type-generic queue using singly linked lists
*/

#include <stdlib.h>
#include <stdio.h>

typedef struct Node {
    void *          data;
    struct Node *   next;
} Node;

typedef struct Queue {
    Node *  head;
    size_t  data_size;
} Queue;

typedef struct Person {
    char const *        name;
    unsigned short int  age;
    char const *        occupation;
} Person;

Queue *create_queue();
void register_new_size(Queue *, size_t data_size);
void enqueue(Queue *, void *data);
void *front(Queue *);
int length(Queue *);
int is_empty(Queue *);
void dequeue(Queue *);
Queue *copy_queue(Queue *);
void print(Queue *);
void destroy_queue(Queue *);

int is_empty(Queue *b)
{
    if(b->head == NULL) { return 1; }
    return 0;
}

Queue *create_queue()
{
    Queue *new_queue = (Queue *)malloc(sizeof(Queue));
    new_queue->head = NULL;
    return new_queue;
}

void destroy_queue(Queue *b)
{
    while(!is_empty(b)) {
        dequeue(b);
    }
    free(b);
}

void enqueue(Queue *b, void *data)
{
    Node *new_node = (Node *)malloc(sizeof(Node));
    new_node->data = malloc(b->data_size);
    memcpy(new_node->data, data, b->data_size);
    new_node->next = NULL;

    if(is_empty(b)) {
        b->head = new_node;
        return;
    }
    Node *n = b->head;
    while(n->next != NULL) {
        n = n->next;
    }
    n->next = new_node;
}

void *front(Queue *b)
{
    return (b->head)->data;
}

int length(Queue *b)
{
    Queue *copy = create_queue();
    register_new_size(copy, b->data_size);
    int count = 0;
    while(!is_empty(b)) {
        enqueue(copy, front(b));
        dequeue(b);
        count++;
    }
    while(!is_empty(copy)) {
        enqueue(b, front(copy));
        dequeue(copy);
    }
    destroy_queue(copy);
    return count;
}

void dequeue(Queue *b)
{
    Node *upcoming = b->head->next;
    free(b->head);
    b->head = NULL;
    if(upcoming != NULL) {
        b->head = upcoming;
    }
}

Queue *copy_queue(Queue *b)
{
    Queue *copy = create_queue();
    register_new_size(copy, b->data_size);
    int count = length(b);
    while(count > 0) {
        void *d = front(b);
        enqueue(copy, d);
        dequeue(b);
        enqueue(b, d);
        count--;
    }
    return copy;
}

void print(Queue *b)
{
    if(is_empty(b)) {
        printf("[empty]\n");
        return;
    }
    Queue *copy = copy_queue(b);
    printf("[");
    while(!is_empty(copy)) {
        struct Person *d = (struct Person *)front(copy);
        printf("%s, ", d->name);
        dequeue(copy);
    }
    printf("]");
    printf("\n");
    destroy_queue(copy);
}

void register_new_size(Queue *b, size_t data_size)
{
    b->data_size = data_size;
}

int main(void)
{
    Queue *queue = create_queue();
    Person chase = { "Chase", 49, "Banker" };
    Person evan  = { "Evan", 34, "Doctor" };
    Person susie = { "Susie", 43, "Teacher" };
    register_new_size(queue, sizeof(Person));
    enqueue(queue, &chase);
    enqueue(queue, &evan);
    enqueue(queue, &susie);
    print(queue);
    dequeue(queue);
    print(queue);
    dequeue(queue);
    print(queue);
    dequeue(queue);
    print(queue);
    destroy_queue(queue);
    return 0;
}

```
\$\endgroup\$
2
  • 2
    \$\begingroup\$ I've since realized that I'm not checking for malloc() returning NULL \$\endgroup\$
    – Mode77
    Aug 2 at 19:52
  • 2
    \$\begingroup\$ Just a minor tip that doesn't feel like it warrants a separate answer: I would suggest that dequeue returns the dequeued data. It allows for use cases like while( data = queue->dequeue() ) { /* do something with data */ ). \$\endgroup\$
    – CompuChip
    Aug 4 at 11:56

4 Answers 4

11
\$\begingroup\$
  • Yes, you don't check the malloc return value. Along the same line, you should not cast it.

  • is_empty implementation is anti-idiomatic. It should be

      return b->head == NULL;
    
  • dequeue from an empty queue dereferences NULL.

  • register_new_size is called uncontrollably, and has no relation to the size of the next data item to be enqueued. You'd be in much less eror prone having

      typedef struct Node {
          void * data;
          size_t size;
          Node * next;
      };
    

    and

      void enqueue(Queue * b, void * data,  size_t data_size);
    
  • length is scarily suboptimal. There is no need create a copy. Consider

      size_t length(Queue * b)
      {
           size_t len = 0;
           Node * cursor = b->head;
           while (cursor) {
               len++;
               cursor = cursor->next;
           }
           return len;
      }
    

    Better yet, make size a member of Queue; increment it on each enqueueing, and decrement it in each dequeuing.

    BTW, notice the type. int may not be wide enough.

  • print_queue has a very limited utility. Consider a more generic

      map(Function f, Queue * q, void * args)
      {
          Node * cursor = q->head;
          while (cursor) {
              f(cursor->data, args);
          }
      }
    

    where Function should be declared along the lines of

      typedef void (*Function)(void *, void *);
    

    As a side note, there are plenty of variations of the theme.

  • enqueue has a linear time complexity. Keeping a tail pointer is a small price to make it constant time (just enqueue at the tail, and dequeue from the head).

\$\endgroup\$
0
9
\$\begingroup\$

Don't cast the result value of malloc(). (In general, using casts in C is a yellow card. Using C-style casts in C++ is a red card)

The reason to cast the result of malloc() is because C++ requires a cast for malloc(), but C doesn't require that.

  1. Using malloc() in C++ is already a red flag, so you don't need to cast the result of malloc()

  2. In C, casting the result of malloc() is actually very harmful.

If you forgot to include <stdlib.h> and you ignore compiler warnings, the result type of malloc() would be implicit int, so you will cast int to Queue*, god knows what will happen. This kind of bug is very hard to spot. If you don't cast, then implicit casting from int to Queue* is not allowed, so the compiler will reject your code for you.

\$\endgroup\$
6
\$\begingroup\$

You've already mentioned in the comments that you should be checking the return value of malloc so I won't mention that further.

  1. To start off with a minor point, since create_queue doesn't take any arguments, you should mark this explicitly via
Queue *create_queue(void);

Also, this function leaves the item_size field uninitialized. You should either have a default value or pass the desired value as an argument.

  1. Since enqueue adds items to the end, it would be more efficient to add a tail field to Queue. That way, you don't need to seek to the end of the list every time you add something.

  2. The function is_empty can be simplified to

int is_empty(const Queue *b)
{
    return (b->head == NULL);
}

since boolean expressions always have the numerical value 1 or 0. Note that I've marked the argument as const as well.

You could even make it a macro:

#define QUEUE_IS_EMPTY(b) ((b)->head == NULL)
  1. With destroy_queue, you call free(b) at the end. That may be fine but consider if you want to allow queues to be created on the stack. I.e.,
Queue b;

If so, then you should remove the call to free from destroy_queue and have that be a separate operation.

  1. You should be checking the arguments of all non-static functions. What if data is NULL in enqueue? You'd crash with a segfault.

  2. This is minor but I recommend changing the name of the Queue* variables to something other than b. Variable names, with the exception of for loop indices, should be descriptive. queue would be a good choice. If you want to use a single letter, why not q?

\$\endgroup\$
5
  • \$\begingroup\$ +1 for all the good points, but I would not have suggested making a macro. \$\endgroup\$
    – G. Sliepen
    Aug 3 at 9:37
  • \$\begingroup\$ Why would you not use a macro? \$\endgroup\$ Aug 3 at 14:34
  • 2
    \$\begingroup\$ See this post for the various pitfalls of macros. Even if your macro looks fine, consider that it doesn't have any type checking (you can apply it to anything that has a head member variable), and it pollutes the global namespace (what if you have implemented other containers that also need an IS_EMPTY() function?). \$\endgroup\$
    – G. Sliepen
    Aug 3 at 14:50
  • 2
    \$\begingroup\$ Adding an assert() or two would not go amiss, but checking pointers point to the appropriate kind and amount of data is generally impossible to check. \$\endgroup\$ Aug 4 at 18:22
  • \$\begingroup\$ Perhaps an inline function? \$\endgroup\$ Aug 6 at 23:18
3
\$\begingroup\$

I later discovered this revision contains a serious error, which is dequeueing frees the space occupied by the head node, but does not first free the space occupied by the head node's data, which leaves the memory block hanging without a reference to it; this is a memory leak.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.