Rellocating/restructing an array of structure efficiently in C

Question

I have an array of structures in C as in (simplified):

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

Then I allocate an array of pointers to this structures as in:

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

So, effectively, I have an array of structures: Now, I have a function that writes to this array and a counter keeps track of the position in the array. Lets say arrayCount;

At some point, I try to flush to disk the elements written in the array of structs but am able to flush only n elements. Where n < arrayCount; So, I am left with arrayCount - n elements in the array.

In the next iteration, I want to start from where I left but in the mean time, more elements will be added to the array. In other words, after I have flushed n element in the array, I want to:

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.

I can create a new array of structs and copy the ones left to be flushed to the beginning of the array but I am looking for something more efficient.

You could use the `memmove` function to safely move/copy the `arrayCount-n` elements to the beginning of the same array. https://en.cppreference.com/w/c/string/byte/memmove — isrnick, May 20 '20 at 15:31
"So, effectively, I have an array of structures". No, you don't. You have an array of pointers. It's not the same thing. — Oppen, May 20 '20 at 17:22
You can just keep the indices to the first and last effective elements. You add after the last one, wrapping around to the start when full, and pop from the start. This way you perform no extra copies. That's called a circular buffer and is one of the most common ways to implement queues. — Oppen, May 20 '20 at 17:25
@isrnick in typical implementations `memmove()` [will not copy the elements to a temporary array](https://stackoverflow.com/a/13339861/13527856) — MarcoLucidi, May 20 '20 at 17:29
Re: my first comment: you're allocating space for `arrayLength` `writeBuffer*` elements, but assigning it as if it was an array of `writeBuffer`. You'll hit out of bounds. — Oppen, May 20 '20 at 17:30
@MarcoLucidi Thank you. So `memmove` would indeed be more efficient after all, since only one copy operation will be made for each element. I'll remove my comment saying otherwise. — isrnick, May 20 '20 at 18:22
@MarcoLucidi Yes. If no temporary array/copy is involved, then memmove suffices to do the job without further ado... — asinix, May 22 '20 at 10:23
Note that the `(struct writeBuffer *)` cast is not required. your code will function without it. — Robert Harvey, May 22 '20 at 14:29

Oppen · Accepted Answer · 2020-05-22T14:22:57.110

Example solution, with comments:

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

Note it's not optimized at all, nor was it tested, so there may be off-by-ones here and there. It's here to illustrate the concept.

As mentioned in one comment, this is called a circular buffer, and has the advantage of working as a bounded (as in memory) queue.

I have a different solution but based upon the approach suggested by you of having circular queues. This avoids the entire issue of copying (as you pointed out) at the relatively less overhead of maintaining indexes of the current status. — asinix, May 22 '20 at 03:58

Rellocating/restructing an array of structure efficiently in C

1 Answers1