c - 在 C 中有效地重新分配/重构结构数组

Question

我在 C 中有一个结构数组，如（简化）：

 typedef struct writeBuffer {
    uint8_t  *buffer;
    struct someOtherStruct mySomeOtherStruct;
    uint32_t length; 
 } writeBuffer;

然后我分配一个指向这个结构的指针数组，如下所示：

 int arrayLength = 20;
 struct writeBuffer *myStructArray;
 myStructArray = (struct writeBuffer *) malloc( arrayLength * sizeof(struct writerBuffer *));

所以，实际上，我有一个结构数组：现在，我有一个写入这个数组的函数，一个计数器跟踪数组中的位置。让我们说arrayCount；

在某些时候，我尝试将写入结构数组中的元素刷新到磁盘，但只能刷新 n 个元素。其中 n < 数组计数；所以，我剩下 arrayCount - 数组中的 n 个元素。

在下一次迭代中，我想从我离开的地方开始，但与此同时，更多的元素将被添加到数组中。换句话说，在我刷新了数组中的 n 个元素之后，我想：

a. Retain the length of the array.
b. Delete the structs which were flushed to disked.
c. Reset the pointer now to the nth element as if it is the first element.
d. As I am keeping track separately of the number of elements left to be flushed, I do not care to zero out other elements in the array.

我可以创建一个新的结构数组并将剩下的结构复制到数组的开头，但我正在寻找更有效的东西。

标签： carraysstruct

Answer 1

示例解决方案，带有注释：

typedef struct {
    // Irrelevant contents.
} MyStruct;

#define BUFFER_SIZE 20
typedef struct {
    MyStruct buffer[BUFFER_SIZE];
    int head, tail;
} MyStructBuffer;

// Returns how many occupied elements b has.
int len(MyStructBuffer *b) {
    // If the head appears after the tail,
    // then we used from head to the end of
    // the array, and since the beginning to
    // the tail. Thus, the length will be the
    // value of tail plus as many elements
    // as head is behind the end of the array.
    // Otherwise, it's the distance between
    // tail and head.
    if (b->head > b->tail)
        return b->tail + (BUFFER_SIZE - b->head);
    return b->tail - b->head;
}

// Tries to flush n elements from buffer b,
// returns how many elements were flushed.
int flush_structs(MyStructBuffer *b, int n) {
    // We won't flush more elements than the
    // buffer has.
    if (n > len(b))
        n = len(b);
    for (int i = 0; i < n; i++) {
        // Flushes one single instance of struct,
        // reading from the beginning of occupied
        // space, pointed by the head index.
        // Advances the head index to discard the
        // flushed element afterwards.
        flush_struct(&b->buffer[b->head++]);
        // Make sure the index remains in the right
        // bounds.
        b->head %= BUFFER_SIZE;
    }
    return n;
}

// Adds element e at the end of b, unless full.
// 0 if unable to add, 1 otherwise.
int add_struct(MyStructBuffer *b, MyStruct *e) {
    if (len(b) == BUFFER_SIZE)
        return 0;
    // Set the last element to *e, then increase
    // the tail index;
    b->buffer[b->tail++] = *e;
    // Make sure the index is within the right bounds.
    b->tail %= BUFFER_SIZE;
    return 1;
}

请注意，它根本没有经过优化，也没有经过测试，所以这里和那里可能会有不同的地方。这是为了说明这个概念。

正如在一条评论中提到的，这称为循环缓冲区，并且具有作为有界（如在内存中）队列工作的优点。