Skip to main content
Code Review

Return to Answer

Mention the tight binding between scale factor and addition to head
Source Link
Toby Speight
Toby Speight
  • 81.8k
  • 14
  • 101
  • 309

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:

queue_iterate has:

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:

Add a section to recommend some tests
Source Link
Toby Speight
Toby Speight
  • 81.8k
  • 14
  • 101
  • 309

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.

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.

Good choice of type for capacity and size. I'd probably have head and tail be pointers to void* rather than indexes. 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).

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.

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.

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.

Source Link
Toby Speight
Toby Speight
  • 81.8k
  • 14
  • 101
  • 309

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

  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.

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.