5
\$\begingroup\$

I'm implementing a generic (ie. void *) queue in C. I believe I have a working version but I'm looking for two things:

  • Do any subtle bugs pop out to the experienced reader?
  • Can I implement this in a better way (perhaps using void ** pointers?

queue.h

#ifndef QUEUE_H
#define QUEUE_H

#include <stdbool.h>
#include <stdlib.h>

typedef struct Queue Queue;

void   queue_free     (Queue* queue);
Queue* queue_init     (void);

void*  queue_dequeue  (Queue* queue);
void   queue_enqueue  (Queue* queue, void* item);

bool   queue_is_empty (const Queue* queue);
void   queue_iterate  (const Queue* queue, void (*fn)(void*));
size_t queue_size     (const Queue* queue);

#endif

queue.c

#include "queue.h"

#include <assert.h>
#include <stddef.h>
#include <stdio.h>

struct Queue {
  size_t capacity, size;
  void** data;
  size_t head, tail;

  /*
    The queue is constructed using a pointer to the data and two integers representing
    the head and tail of the queue.

    head, tail
    |
    v
    [ ][ ][ ][ ]

    When an item is enqueued, we place it at the tail of the list and increment the tail.    

    head
    |  tail
    v  v
    [a][ ][ ][ ]

    The tail is guaranteed to always point to an empty slot (if it can't point to an empty
    slot, the underlying array is resized).

    head            head
    |               |           tail 
    v               v           v
    [a][b][c][d] => [a][b][c][d][ ][ ][ ][ ]

    If the tail has reached the end of the underlying array (and there is still room), it
    wraps around.

    tail
    |  head
    v  v
    [ ][b][c][d]

    When an object is dequeued we return the item pointed to by head and increment head. If
    the queue is empty, we do _not_ move head.

    tail
    |     head
    v     v
    [ ][ ][c][d]

    If, when we resize the array, head is larger than tail, we move all of head's elements to
    the end of the new array.

    tail
    |                 head
    v                 v
    [c][d][ ][ ][ ][ ][a][b]
  */
};

void queue_free(Queue* queue) {
  assert(queue);  
  free(queue->data);
  free(queue);
}

Queue* queue_init(void) {
  Queue* queue = calloc(1, sizeof *queue);
  assert(queue);  
  queue->capacity = 100;
  queue->size = 0;
  queue->data = calloc(queue->capacity, sizeof *queue->data);
  assert(queue->data);
  queue->head = 0;
  queue->tail = 0;
  return queue;
}

void* queue_dequeue(Queue* queue) {
  assert(queue);
  if (queue->size == 0) {
    return NULL;
  }
  void* item = queue->data[queue->head];
  queue->head = (queue->head + 1) % queue->capacity;
  queue->size--;
  assert(item);
  return item;
}

void queue_enqueue(Queue* queue, void* item) {
  assert(queue);
  assert(item);
  queue->data[queue->tail] = item;
  queue->size++;

  // Resize the underlying array if we've reached capacity.
  if (queue->size == queue->capacity) {
    size_t scale = 2;
    void** tmp = realloc(queue->data, scale * queue->capacity * sizeof *tmp);
    assert(tmp);
    if (queue->head > queue->tail) {
      for (size_t i = queue->head; i < queue->capacity; ++i) {
        tmp[i + queue->capacity] = tmp[i];
        tmp[i] = NULL;
      }
      queue->head += queue->capacity;
    }
    queue->capacity *= scale;
    queue->data = tmp;
  }

  queue->tail = (queue->tail + 1) % queue->capacity;
}

bool queue_is_empty(const Queue* queue) {
  assert(queue);
  return queue->size == 0;
}

void queue_iterate(const Queue* queue, void (*fn)(void*)) {
  assert(queue);
  assert(fn);

  if (queue->size == 0) {
    return;
  }
  for (size_t i = 0; i < queue->size; ++i) {
    void* x = queue->data[(i + queue->head) % queue->capacity];
    fn(x);
  }
}

size_t queue_size(const Queue* queue) {
  assert(queue);  
  return queue->size;
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I made a few edits of bugs I've just seen after posting and added a bit of an explanation in the source file. \$\endgroup\$
    – sdasdadas
    Feb 26, 2021 at 23:58

1 Answer 1

5
\$\begingroup\$

I like your diagrams in the comments - a picture really can express much more than words sometimes! It's a shame the text lines are so long - I recommend keeping line lengths less than a standard terminal width of 80 columns (even in these days of large monitors, most readers prefer to have more files visible side-by-side than to have longer lines in each).


struct Queue {
  size_t capacity, size;
  void** data;
  size_t head, tail;
};

Good choice of type for capacity and size. I'd probably have head and tail be pointers to void* rather than indexes, but either is a valid design choice.

Keeping a record of head, tail and size is somewhat redundant. Instead of maintaining size as a member, we could compute it when needed from head and tail, provided we don't ever completely fill the queue (i.e. expand it just before head==tail, rather than just after). Alternatively, we could dispense with either head or tail, and generate the value from the other one and size.


  Queue* queue = calloc(1, sizeof *queue);
  assert(queue);

That's plain wrong. We know that calloc() can return zero, so claiming queue is non-zero is mistaken.

It seems that you think assert() is a tool for run-time checks, but that is not the case. assert() exists to document things we know to be true (and, in debug builds, let us know when our claims are wrong).

The correct code is

  Queue* queue = calloc(1, sizeof *queue);
  if (!queue) { return queue; }

Not only does this perform the check in non-debug builds, it reports the failure to the caller, who can handle it appropriately.

Such misuse of assert() exists throughout the program.

It's not clear why we're using calloc() here rather than malloc() - we write all the storage we allocate, so the zero-initialising done by calloc() is just a waste of cycles.


void queue_free(Queue* queue) {
  assert(queue);  
  free(queue->data);

Why not just handle a null queue, to give an interface consistent with free()? I'd write

void queue_free(Queue* queue)
{
    if (!queue) { return; }
    free(queue->data);
    free(queue);
}

That makes life much easier for callers, who can now pass their Queue* to queue_free() without needing a separate path for null pointers.


if (queue->head > queue->tail) {
  for (size_t i = queue->head; i < queue->capacity; ++i) {
    tmp[i + queue->capacity] = tmp[i];
    tmp[i] = NULL;
  }
  queue->head += queue->capacity;
}

I think the loop there can be replaced by a simple memmove(). There should be no need to assign NULL to the positions between tail and head, as we'll not access those entries before they are next written.


There's a subtle connection between two parts of the code here:

size_t scale = 2;
if (queue->head > queue->tail) {
  /* copy elements */
  queue->head += queue->capacity;
}
queue->capacity *= scale;

That scale factor of 2 and the addition of queue->capacity are tightly bound, yet if we were to change the scale factor to 3, or (also changing its type) to 1.5, we wouldn't necessarily spot that we need to update the addition to match. We could write

  queue->head += queue->capacity * (scale - 1);

Alternatively, we could introduce a new variable instead of scale:

  new_capacity = queue->capacity * 2;
  queue->head += new_capacity - queue->capacity;

This version makes it easier to use rational scale factors using integer arithmetic (queue->capacity * 3 / 2, for example).


queue_iterate has:

  if (queue->size == 0) {
    return;
  }

That's unnecessary, since the rest of the function is a for loop that will do nothing when size is zero. We can just omit this test.


One thing missing that I would have liked to have seen is a comprehensive set of unit tests. It's much better to demonstrate correctness by testing than by inspection, and self-contained library code such as this is highly suited to unit testing.

A good test suite also gives confidence to make improvements to the code with minimal risk of introducing regressions to previously-working functions.

Whenever a bug is found, it's good to reproduce it by adding a new test. Then fix the bug to make the test pass.

Occasionally, run the test suite using a profiler or checker such as Valgrind. Depending on the checker, that can reveal memory leaks or other allocation problems, cache performance, or many other run-time aspects of the code.

\$\endgroup\$
5
  • 2
    \$\begingroup\$ This is a great review. I think the decision to have head and tail be size_t over a pointer is very valid, and I would have done the same as OP; this avoids stale pointers when realloc is called in queue_enqueue. \$\endgroup\$
    – Neil
    Feb 28, 2021 at 23:03
  • 2
    \$\begingroup\$ Yes, index or pointer are both valid choices. Similarly, which two of head, tail, size we need to keep is also a design choice. I do really need to be clearer about different levels of recommendation. \$\endgroup\$ Mar 1, 2021 at 8:22
  • \$\begingroup\$ Thanks very much @TobySpeight, this was (again) incredibly helpful. I think I have been using asserts to debug but it's a fair criticism that in some spots it's just as easy to write the actual error handling code the first time around. I've been missing unit testing while writing C code so that's another good suggestion that I need to incorporate. \$\endgroup\$
    – sdasdadas
    Mar 1, 2021 at 19:06
  • 1
    \$\begingroup\$ I quite often test my C code using a C++ unit-test framework. It's easy to call C functions from C++, and there are some good C++ test frameworks around. \$\endgroup\$ Mar 1, 2021 at 21:04
  • \$\begingroup\$ That's a good suggestion -- I've been trying out C++ for some niceties like function overloading so I'll include that in the pro section as well. I played with Unity yesterday and it seems to be simple enough as long as I remember to add tests to the suite. \$\endgroup\$
    – sdasdadas
    Mar 2, 2021 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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