Re allocating C array for more space

Question

Im writing a program with a function add(a , i, n) which will add 'i' as an element to 'a', but if the array 'a' runs out of space, then I need to realloc more memory to the array. Im stuck here:

#include <stdlib.h>
#include <stdio.h>

int add(int* a, int i, int n);

int main(){
    int n = 20;
    int *a = (int*) malloc(n*sizeof(int));
    int i;

    for (i = 0; i < 100000; i++){
        n = add(a, i, n);
        printf("a[%d]=%d\n",i,(int)a[i]);
    }
    return 0;
}

int add(int *a, int i, int n){
    if (i >= n){
        n++;
        int* b = (int*) realloc(a, n*sizeof(int));
        a[i]=i;
        return n;
    }else{
    }
}

Im not very experienced so please be gentle...

You never use the return value of `realloc`, also it seems that you want to change `main::a`, in this case you have to pass the address of `a` to `add`. — mch, Jul 10 '18 at 06:47
[This `realloc` reference](http://en.cppreference.com/w/c/memory/realloc) should be helpful. Summary: After the call to `realloc`, `a` may no longer be valid. — Some programmer dude, Jul 10 '18 at 06:47
I realized I had been experimenting and forgot to return my code to its previous state. That realloc reference seems to be what I'm looking for, Ill mess around with that. Thanks. — Adam Mattaway, Jul 10 '18 at 06:55

score 1 · Accepted Answer · answered Jul 10 '18 at 07:08

realloc tries to reallocate the given memory, but sometimes, it can't and gives you a new memory pointer.

It must be used like:

int *b;
b = realloc(a, <newsize>);
if (b) {
    /* realloc succeded, `a` must no longer be used */
    a = b;
    /* now a can be used */
    printf("ok\n");
} else {
    /* realloc failed, `a` is still available, but it's size did not changed */
    perror("realloc");
}

Now, you still have some trouble in your code:

The idea of function add() is to reallocate a when needed, but a is given by copy, so its value won't be changed in main.

#include <stdlib.h>
#include <stdio.h>

int add(int** a, int i, int n);

int main(){
    int n = 20;
    int *a = malloc(n*sizeof(int));
    int i;

    for (i = 0; i < 100000; i++) {
        /* note how `a` is passed to `add` */
        n = add(&a, i, n);
        printf("a[%d]=%d\n",i,a[i]);
    }
    /* and finally free `a`*/ 
    free(a);
    return 0;
}

/* changed `a` type to make its new value visible in `main` */
int add(int **a, int i, int n){
    if (i >= n){
        /* want to write a[i], so size must be at least i+1*/
        n = i+1;
        /* realloc memory */
        int *b = realloc(*a, n*sizeof(int));

        /* check that `realloc` succeded */
        if (!b) { 
            /* it failed!*/
            perror("realloc"); 
            exit(1);
        } 
        /* store new memory address */
        *a = b;
    }

    /* update memory */        
    (*a)[i]=i;        

    /* return new size */
    return n;
}

Note: I removed malloc/realloc cast, see: Do I cast the result of malloc?

Thank you so much for helping out. Your right, I was referencing a copy not the actual pointer. Ill fix my code, ty ty — Adam Mattaway, Jul 10 '18 at 07:35

bobah · Answer 2 · 2018-07-11T06:20:41.270

To have an automatically growing array in C you would normally need a helper function ensure_capacity to take care of the array reallocation.

The helper function would preferrably reallocate using 2x grow policy, so you have an amortized constant time of the append operation.

The code would look somewhatlike the below.

Note that the code is using the first 2 elements of the array to keep its capacity/size. You can use a struct of pointer + size instead, but you need to keep the two close two each other as otherwise the code won't be easy to read.

int* ensure_capacity(int* vec, int new_cap) {
    if (vec == 0) {
        vec = (int*) malloc(18 * sizeof(int));
        vec [0] = 16;
        vec [1] = 0;
    } else {
        int cap = vec[0];
        if (cap < new_cap) {
            do {
                cap *= 2;
            } while (cap < new_sz);
            int* new_vec = (int*) realloc(vec, cap * sizeof(int));
            if (new_vec != null) {
                vec = new_vec;
                vec[0] = cap;
            } else {
                // reallocation failed, handle the error
            }
        }
    }
    return vec;
}

And you would use it in your add() function like:

int* push_back(int* vec, int val) {
    vec = ensure_capacity(vec, vec[1] + 1);
    vec[vec[1]++] = val;
    return vec;
}

setting vec inside `push_back` has no sense, you need the argument to be `int** vec` argument and write into it with `*vec = ...`. You are also not checking if `realloc` fails — dfogni, Jul 10 '18 at 07:15
@dfogni - you should accept existence of different coding styles. I prefer a return value notation over in/out parameters, as I find it easier to read. — bobah, Jul 10 '18 at 07:52
@bobah it has nothing to do with coding style. the proposed `push_back` is complelely wrong. how should the caller know where the reallocated array is? how should it know if reallocation failed? — dfogni, Jul 10 '18 at 10:17

Re allocating C array for more space

2 Answers2