Realloc initially works, then returns null after several repetitions

Question

Realloc initially works for array sizes 200 and 400, but then unexpectedly returns null at size 800 for reasons I cannot parse.

Unsigned long ints in use because of that massive m value and are very much necessary. Probably.

I'm embarrassingly bad at C.

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

/* Macros */
#define m    4294967161
#define a    2
#define r    (m % a)
#define q    (unsigned long) floor(m / a)

/* Method stubs */
[snip]

/* Initial array settings */
unsigned long elements = 0;   // Number of elements in the array.
unsigned long size = 100;     // Dynamically allocated size of the array.

/* Evaluates g(x) = ax mod m with no values > m - 1 */
unsigned long g(unsigned long x) {
    [snip]
}

unsigned long compute() {
    unsigned long i = 1;
    unsigned long x = a;
    unsigned long j = 0;
    unsigned long *multipliers = 0;
    initialize(&multipliers);

    while (x != 1) {
        if (((m % x) < (m / x)) && (gcd(i, m - 1) == 1)) {
            add(x, multipliers);
            j++;
        }
        i++;
        x = g(x);
    }
}

/* Initialize array. */
void initialize(unsigned long **multipliers) {
    *multipliers = (unsigned long *)malloc(sizeof(unsigned long) * size);
}

/* Add element to an array. */
void add(unsigned long element, unsigned long *multipliers) {
    if (elements >= size) {
        printf("Inside elements >= size check.\n");
        size = size * 2;
        printf("Size is now %lu\n", size);
        unsigned long *n_vector = NULL;
        n_vector = (unsigned long *)realloc(multipliers, sizeof(unsigned long) * size);
        printf("Reallocated.\n");

        if (n_vector != NULL) {
            printf("Copying n_vector to multipliers.\n");
            multipliers = n_vector;
        }
        else
            printf("n_vector is null.\n");
    }
    multipliers[elements++] = element;
    return;
}

And what was the output of `printf("Size is now %lu\n", size);` and other `printf()`? — chux - Reinstate Monica, Sep 30 '15 at 20:54
With `m` and `a` being (unsigned) integers, `m / a` is always 'floored' (technically truncated, but with them always positive it's equivalent to flooring), so using `floor` and the cast aren't necessary. Also: no need to [cast the result of `malloc`](http://stackoverflow.com/a/605858/249237) or `realloc`. — Kninnug, Sep 30 '15 at 20:55
`q`, as `#define q (unsigned long) floor(m / a)` is scary. Although not used in posted code, I would use `#define q ((unsigned long) floor(m / a))` to prevent unexpected precedence rule effects. — chux - Reinstate Monica, Sep 30 '15 at 21:01
When reallocating, you need a pointer to pointer. (multipliers is a pointer) The initialise function does this correct. Since you already have a global pointer, it is maybe better *not* to pass (a pointer to) it as a argument to the resize function? — wildplasser, Sep 30 '15 at 21:02
@wildplasser Nice. `multipliers` in `add(x, multipliers);` is not updated. — chux - Reinstate Monica, Sep 30 '15 at 21:06
BTW: The argument shadows the global name, too. Just removing the argument from the function "signature" would possibly make things work. — wildplasser, Sep 30 '15 at 21:10
i guess you want to have `elements` and `size` and the array inside of a `struct`. otherwise it doesn't make sense to just pass the array around while having its related data to be global. — Jason Hu, Sep 30 '15 at 21:23

score 4 · Answer 1 · answered Sep 30 '15 at 21:14

Here's the problematic part of your code:

void add(unsigned long element, unsigned long *multipliers) {
        n_vector = realloc(multipliers, sizeof(unsigned long) * size);
        multipliers = n_vector;
}

On entry, multipliers is a pointer to a buffer allocated by malloc. You call realloc, which returns the new address of the buffer. The new address may or may not be equal to the old one. You then set the local variable multipliers to the new address. But that's a local variable. When the function returns, the new address is not stored anywhere. The caller of this function (the compute function) is still using the old address.

After the first call to realloc that changes the address, you might initially not notice anything, because the old address still has the old content; but when you write past the old end, you're potentially overwriting data structures used by the memory management system. At the point where you call realloc again, the parameter that you pass to it is the address of the old buffer, which, at this point, no longer points to a buffer that malloc/realloc are managing. At this point, all hell breaks loose.

Solution: add needs to return the new address to its caller. Either make it return it (you can since it's currently returning nothing), or pass the multipliers pointer to it as a reference rather than a value — in other words, in C, make the argument a pointer to a pointer. Here are the main relevant lines in the second approach:

void add(unsigned long element, unsigned long **multipliers) {
    …
    n_vector = realloc(*multipliers, sizeof(unsigned long) * size);
    if (n_vector == NULL) {
        … // error handling
    } else {
        *multipliers = n_vector;
    }
}

void compute() {
     …
     add(x, &multipliers);
     …
}

Realloc initially works, then returns null after several repetitions

1 Answers1