Вопрос о реализации C циклического буфера

Question

Я видел следующую реализацию циклического буфера:

http://en.wikipedia.org/wiki/Circular_buffer

/**< Buffer Size */
#define BUFFER_SIZE    10
#define NUM_OF_ELEMS   (BUFFER_SIZE-1)

/**< Circular Buffer Types */
typedef unsigned char INT8U;
typedef INT8U KeyType;
typedef struct
{
    INT8U writePointer; /**< write pointer */
    INT8U readPointer;  /**< read pointer */
    INT8U size;         /**< size of circular buffer */
    KeyType keys[0];    /**< Element of circular buffer */
} CircularBuffer;

/**< Init Circular Buffer */
CircularBuffer* CircularBufferInit(CircularBuffer** pQue, int size)
{
    int sz = size*sizeof(KeyType)+sizeof(CircularBuffer);
    *pQue = (CircularBuffer*) malloc(sz);
    if(*pQue)
    {
        printf("Init CircularBuffer: keys[%d] (%d)\n", size, sz);
        (*pQue)->size=size;
        (*pQue)->writePointer = 0;
        (*pQue)->readPointer  = 0;
    }
    return *pQue;
}

int main(int argc, char *argv[])
{
    CircularBuffer* que;
    KeyType a = 101;
    int isEmpty, i;

    CircularBufferInit(&que, BUFFER_SIZE);
    ...
}

Вот вопросы:

Q1> Почему код использует следующую строку для определения переменной keys ?

KeyType keys[0];    /**< Element of circular buffer */

Q2> Почему код вычисляет размер выделенного буфера следующим образом:

int sz = size*sizeof(KeyType)+sizeof(CircularBuffer);

Q3> Почему pQue указывает на буфер больше, чем размер CircularBuffer, но все еще может напрямую ссылаясь на члена этого?

(*pQue)->size=size;
(*pQue)->writePointer = 0;
(*pQue)->readPointer  = 0;

Answer 1

Первый элемент - просто указать, что элемент в структуре использует синтаксис массива, но на самом деле он не объявлен как массив любого размера.

Malloc выделяет круговой размер буфера (который учитывает все неключевые поля) и ключевые поля (size * sizeof (KeyType)). Обратите внимание, что ключи [0] на самом деле имеют нулевой размер, поэтому ни одно поле ключа не учитывается дважды.

Буфер на самом деле не больше, чем размер циклического буфера, выделение (как описано выше) было однократным выделением для размещения циклического буфера и элементов управления (size, readPointer, writePointer) за один проход .

Вся причина в том, что это работает, потому что C не проверяет, прошел ли ты конец массива. В языке, который устанавливает границы массивов, при первой попытке использовать это вы получите что-то похожее на ArrayOutOfBoundsException в Java, потому что для использования keys [0] вы должны были бы объявить массив ключей размером (по крайней мере) один, как клавиши [1].

Другими словами, это пара специфичных для C хаков, чтобы оптимизировать распределение буфера один раз, без кодирования фиксированного размера. Это работает потому, что смещение массива строго реализовано как (базовый адрес + индекс * sizeof (тип массива)).

Answer 2

Этот код реализует то, что иногда называют «эластичным массивом».Цель состоит в том, чтобы создать структуру, содержащую массив, когда размер, если массив не известен во время компиляции.Таким образом, структура определяется с массивом нулевого размера в качестве последнего элемента.Когда он выделен, желаемый размер добавляется к вызову malloc.Поскольку C гарантирует, что блоки malloc будут смежными, и поскольку он не выполняет проверку границ массива, можно индексировать 0 после окончания в дополнительную память и обрабатывать его как обычный элемент массива.

Примечаниечто эта техника работает только тогда, когда вы Malloc структуры.Если он объявлен как локальная переменная, для массива не будет дополнительного места.

Answer 3

Что происходит, так это то, что в начале блока памяти есть структура заголовка, за которой следует переменное количество структур детализации.Раньше это был обычный способ делать вещи, еще в старые времена;вы можете создать все структуры одним вызовом malloc (), так что это хорошо для производительности.Вы, вероятно, также часто будете видеть этот шаблон с кодом обработки файлов или сетевыми протоколами, где вы получите кусок данных переменного размера, точный размер которого указан в заголовке.(Как в формате Excel BIFF, так и в TCP

1: массив нулевой длины обычно использовался для определения массива переменной длины в конце структуры.

2: этовыделение байтов sizeof (CircularBuffer) для заголовка и размера * sizeof (KeyType), чтобы можно было иметь столько KeyTypes. В итоге получается один блок памяти, который содержит как заголовок, так и ключи.

3Ничего плохого в том, чтобы указывать на области ВНЕ выделенного блока памяти. Если бы он указывал НАЗАД за пределами выделенной области, это было бы плохо, но это не так.

Answer 4

int sz = size*sizeof(KeyType)+sizeof(CircularBuffer);

size = количество элементов в циклическом буфере

sizeof (KeyType) = размер одного элемента KeyType

(size * sizeof) = общий объем пространства для хранения всехэлементы KeyType

sizeof (CircularBuffer) = потому что круговой буфер хранит дополнительные поля, чем элементы кругового буфера

Почему код использует следующую строку для определения переменных ключей?

KeyType keys [0];/ ** <Элемент кольцевого буфера * / </p>

Я не могу понять ваши сомнения здесь.Это довольно часто.Круговой буфер представлен массивом элементов, типом которых является KeyType.Если вам интересно, почему он использует KeyType вместо напрямую неподписанного int, это потому что:

1. Таким образом, это более понятно.Новый тип вводит точную информацию о том, для чего предназначен массив.
2. Рефакторинг: если мы решим изменить тип KeyType, мы можем просто изменить typedef.