C Dynamic Array Inserting in the Middle

Question

Heyo. In my C program, im dealing with lots of operations in which i have to read files, and store its data in arrays. For that, as the array handling in C is a little bit complicated, i'm using the following code suggested in this post:C dynamically growing array

typedef struct {
    float *array;
    size_t used;
    size_t size;
} points;

void initArrayInd(arrayInd *a, size_t initialSize) {
    a->array = (GLubyte *)malloc(initialSize * sizeof(GLubyte));
    a->used = 0;
    a->size = initialSize;
}

void insertArrayInd(arrayInd *a, GLubyte element) {
    if (a->used == a->size) {
        a->size *= 2;
        a->array = (GLubyte *)realloc(a->array, a->size * sizeof(GLubyte));
    }
    a->array[a->used++] = element;
}

void freeArrayInd(arrayInd *a) {
    free(a->array);
    a->array = NULL;
    a->used = a->size = 0;
}

I'm used to Java programming, so my way of thinking how should i code the things is, in most of the cases, wrong. I want to, based on this dynamic array allocation, be able to create a new function that will insert me a record in the position i have specified. I want to know what is the best way to do so.

Should i insert the the new record at the end of the array, and then shift everything one position. Should i create a new array, copy the i-1 elements, then place i and copy the i+n elements. Should i split the initial array into two, create a third and mix everything together. What is the best way in C to accomplish so?

EDIT: This would do it?

void insertFPointsAt(points *a, float element, int position) {
    if (a->used == a->size) {
        a->size *= 2;
        a->array = (float *)realloc(a->array, a->size * sizeof(float));
    }
    memmove(&a->array[position], &a->array[position+1], &a->array[a->used] - &a->array[position]);
    a->array[position] = element;
}

You don't need to cast the return value of `malloc` in a C program. Something tells me `sizeof(GLubyte)` is `1`, too. — Carl Norum, Apr 28 '13 at 20:20
If you want to insert at 'middle' indices in your data structure, an array might not be the best choice. Are you stuck using it that way for some reason? — Carl Norum, Apr 28 '13 at 20:21
Yes. I have been using arrays in my program, and i simply need to add a new functionality that involves the insertiong of new points in the middle of a Vertex array. And the OpenGl function i'm using only accept arrays as inputs to create buffers with points to render the scene. I'm stucked with arrays. Preferebly,i would like to do it in C style, not using , but arrays. Not in the middle, anywhere — Nick Spot, Apr 28 '13 at 20:24
Yeah, I meant "middle" as in "not the beginning or the end". Doing the copying is the only game in town, then. Let me write up an answer for you. — Carl Norum, Apr 28 '13 at 20:27
You dont need to, i just want to know what is the best approach, and if i can avoid the tipical for-loops for the purpose, just by using and increment pointers — Nick Spot, Apr 28 '13 at 20:31
You can use `memmove` instead of the for loops. If you're (very) lucky, it might be implemented as a DMA operation and could be much faster than a CPU-bound loop, or at least allow other code to to run. — Carl Norum, Apr 28 '13 at 20:32
Ok. Thanks. To be honest, i'm not very used to C as it is so diferent from oo java. In my C program, i'v not writen a single class, and basically no methods with return, just doing it using extern and global variables and pointers. I'm not sure if it is the best approach, but i'm doing like that — Nick Spot, Apr 28 '13 at 20:36

Sergey Kalinichenko · Accepted Answer · 2013-04-28T21:15:36.377

4

When you insert in the middle of the array, you need to implement this algorithm:

Check if you have enough space for the element that you want to insert
If you do not have enough space, extend the array the way that you do when you add an element at the end
Move the data up by one position using memmove
Place the element at the position requested by the caller

The only step that's different from inserting at the end is the third one, where you move the content of your array up by one element. memmove function deals with this correctly even when the two areas overlap.

EDIT: The memmove call should look like this:

memmove(&a->array[position+1], &a->array[position], &a->array[a->used] - &a->array[position]);

A few additional notes:

Growing the array to twice the size is not going to work after freeing the array, because you set the size to zero.
Unlike C++ where a cast of malloc is required, C does not require you to cast the return value of malloc/calloc/realloc.

edited Apr 28 '13 at 21:15

answered Apr 28 '13 at 20:35

Sergey Kalinichenko

714,442
84
1,110
1,523

okiz, thank you. can you add a small note on how to use memmove? – Nick Spot Apr 28 '13 at 20:39
1

@JohnHarrod I put in a link to the documentation page explaining how to use `memmove`, it's really straightforward: you give it the address from which to move the data, the address to which to move the data, and the length of the region to move. All three should be easy to calculate given the `array` address, the offset, and the current length of the array. – Sergey Kalinichenko Apr 28 '13 at 20:41
@JohnHarrod Oops, I just fixed at link, it was pointing to a wrong function before. Here is the link again: [link to `memmove`](http://pubs.opengroup.org/onlinepubs/009695399/functions/memmove.html). – Sergey Kalinichenko Apr 28 '13 at 20:45
so the memmove would be something like this: memmove(&a->array[position], &a->array[a->used], &a->array[a->used] - &a->array[position]); ? – Nick Spot Apr 28 '13 at 21:04
check my post iv added the code. Just tell me if everything looks alright. – Nick Spot Apr 28 '13 at 21:06
@JohnHarrod Take a look at the edit. Your code moves the data to an incorrect address: you need to move it over by one position - from `&array[position]` to `&array[position+1]`. – Sergey Kalinichenko Apr 28 '13 at 21:18
@JohnHarrod I swapped the first and the second argument of the call to `memmove`: the destination goes first, while the source goes second. – Sergey Kalinichenko Apr 28 '13 at 21:39

score 1 · Answer 2 · answered Apr 28 '13 at 20:33

You only ever need to shift the elements after the index you're trying to insert. Where you'll run into unnecessary copying is when you resize the array - the realloc call might do a copy for you, and you'd end up copying twice. I'd do something like:

insert element E at index I:
   if resize is necessary:
       - allocate new larger buffer
       - copy elements 0 to I-1 from old buffer into new buffer
       - insert E at index I of new buffer
       - copy elements I to end of old buffer into new buffer, starting at index I+1
       - free old buffer
   else
       - copy elements I to end of buffer 'up by one' index
       - insert E at index I of the buffer

C Dynamic Array Inserting in the Middle

2 Answers2