Need some code snippet advice

Question

I wrote the "insert" function to insert an integer into an array of integers. It works, but I don’t know if it is the best algorithm.

Here is my code:

int* insert(int *dest, size_t len, unsigned int index, int value) { int x = 0, i = 0; int *stackp = calloc(len+1, sizeof(int)); if(index > (len-1)) return dest; while(x < len) { if(x == index) { ++x; } else { *(stackp+x) = *(dest+i); ++x, ++i; } } *(stackp+index) = value; free(dest); dest = stackp; return dest; } 

Answer 1

There is a big mistake in memory allocation. stackp is an automatic (stack) array, which means that its lifetime expires as soon as the insert returns. You must use a different distribution method. You can force the caller to allocate a new array and pass both pointers, or you can do it yourself with malloc (remember to free).

However, everything looks good. This is almost the only non-local insertion algorithm. You can do this a little faster with special tricks (for example, copying two ints at once). memmove and memcopy can use such optimizations on some architectures.

In addition, many algorithms will write stackp[index] when the position is found, and not at the end. But the basic algorithm is basically the same.

An alternative would be to insert in place (offset only elements after the insertion position) instead of using a new array. You often expand with realloc . This would be preferable in many situations, as it saves copying time and avoids the malloc new memory cell (which can also fragment the heap).

Finally, an alternative data structure is a fully linked list. This completely eliminates the need to copy items, but uses more memory and prevents accidental access.

Answer 2

There is a serious mistake here. The stackp array is a local variable, and you return it as a result. You will probably get a segmentation error if you want to read / write this array again outside the insert function.

To fix this, you need to allocate a dynamic array, for example:

int *stackp;

stackp = (int *) malloc (size (int) * (len + 1));