Общая очередь в C

Я реализую общий (т.е. void *) в C. Я считаю, что у меня есть рабочая версия, но я ищу две вещи:

• Выскакивают ли опытному читателю какие-нибудь тонкие ошибки?
• Могу ли я реализовать это лучше (возможно, используя void ** указатели?

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

Мне нравятся ваши диаграммы в комментариях — иногда картинка действительно может выразить гораздо больше, чем слова! Жаль, что текстовые строки такие длинные — я рекомендую сохранять длину строк меньше стандартной ширины терминала в 80 столбцов (даже в наши дни больших мониторов большинство читателей предпочитают, чтобы рядом было больше файлов, чем иметь более длинные строк в каждом).

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

Хороший выбор типа для capacity и size. Я бы, наверное, имел head и tail быть указателями на void* а не индексы. Вместо того, чтобы поддерживать size как участник, мы могли вычислить его, когда это необходимо, из head и tail, при условии, что мы никогда не заполним очередь полностью (т.е. не расширим ее непосредственно перед head==tail, а не сразу после).

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

Это совершенно неправильно. Мы знаем это calloc() может вернуть ноль, поэтому требуя queue не равно нулю, ошибочно.

Кажется, ты думаешь assert() это инструмент для проверки во время выполнения, но это не так. assert() существует для документирования того, что мы знаем, чтобы быть правдой (и в отладочных сборках сообщайте нам, когда наши утверждения неверны).

Правильный код

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

Это не только выполняет проверку в неотладочных сборках, но и сообщает об ошибке вызывающей стороне, которая может обработать ее соответствующим образом.

Такое злоупотребление assert() существует на протяжении всей программы.

Непонятно, почему мы используем calloc() здесь, а не malloc() — мы записываем всю память, которую мы выделяем, поэтому инициализация нуля выполняется calloc() это просто пустая трата циклов.

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

Почему бы просто не обработать нуль queue, чтобы интерфейс соответствовал free()? Я бы написал

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

Это значительно упрощает жизнь абонентам, которые теперь могут передавать свои Queue* к queue_free() без необходимости отдельного пути для нулевых указателей.

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

Думаю, там шлейф можно заменить на простой memmove(). Не должно быть необходимости назначать NULL на позиции между tail и head, так как мы не получим доступ к этим записям, пока они не будут записаны в следующий раз.

queue_iterate имеет:

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

В этом нет необходимости, поскольку остальная часть функции является for цикл, который ничего не будет делать при нулевом размере. Мы можем просто пропустить этот тест.