Type-generic queue implementation using singly linked lists

Question

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; } ```

Answer 1

• 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).

Answer 2

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.

Answer 3

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.

2. 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.

3. 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) 

4. 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.

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

6. 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?

Answer 4

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.