Strange behaviour on Realloc: invalid next size

Question

I know there are tons of other realloc questions and answers and I have read almost all of them, but I still couldn't manage to fix my problem.

I decided to stop trying when I accidentaly discovered a very strange behaviour of my code. I introduced a line to try something, but although I don't use the value of newElems in main, the line changes the behaviour.

When the line is commented, the code fails at first realloc. Including the line, the first realloc works. (it still crashes on the second one).

Any ideas on what might be happening?

int main(int argc, char** argv) {
    Pqueue q = pqueue_new(3);
    Node a = {.name = "a"}, b = {.name = "b"},
         c = {.name = "c"}, d = {.name = "d"};

    push(& q, & a, 3);
    // the next one is the strange line: as you can see, it doesn't modify q
    // but commenting it out produces different behaviour
    Pqueue_elem* newElems = realloc(q.elems, 4 * q.capacity * sizeof *newElems);
    push(& q, & b, 5);
    push(& q, & c, 4);

    char s[5];
    Node* n;
    for (int i = 1; i <= 65; ++i) {
        sprintf(s, "%d", i);
        n = malloc(sizeof *n);
        n->name = strdup(s);
        push(& q, n, i);
    }

    Node* current = NULL;
    while ((current = pop(& q))) {
        printf("%s ", current->name);
    }
    return 0;
}

and the push function:

void push(Pqueue* q, Node* item, int priority) {
    if (q->size >= q->capacity) {
        if (DEBUG)
            fprintf(stderr, "Reallocating bigger queue from capacity %d\n",
                    q->capacity);
        q->capacity *= 2;
        Pqueue_elem* newElems = realloc(q->elems,
                                        q->capacity * sizeof *newElems);
        check(newElems, "a bigger elems array");
        q->elems = newElems;
    }

    // append at the end, then find its correct place and move it there
    int idx = ++q->size, p;
    while ((p = PARENT(idx)) && priority > q->elems[p].priority) {
        q->elems[idx] = q->elems[p];
        idx = p;
    }
    // after exiting the while, idx is at the right place for the element
    q->elems[idx].data = item;
    q->elems[idx].priority = priority;
}

The pqueue_new function:

Pqueue pqueue_new(unsigned int size) {
    if (size < 4)
        size = 4;
    Pqueue* q = malloc(sizeof *q);
    check(q, "a new queue.");
    q->capacity = size;
    q->elems = malloc(q->capacity * sizeof *(q->elems));
    check(q->elems, "queue's elements");

    return *q;
}

Answer 1

realloc will change the amount of memory that is allocated, if needed. It is also free to move the data to another place in memory if that's more efficient (avoiding memory fragmentation).
The function, then, returns a new pointer to the new location in memory where your data is hiding. You're calling realloc, and allocating (probably) four times as much memory as before, so it's very likely that that allocated memory is situated elsewhere in memory.

In your comment, you said realloc works like free + malloc. Well, in some cases it can behave similarly, however: realloc and free are different functions, that do different tasks. Both are functions that manage the dynamic memory, so yes, obviously there are similarities, and in the case of realloc, sometimes they can seem to be doing the same thing, however: As I explained here, realloc and free are fundamentally different functions

However, by not assigning the return value of realloc to q.elems, you're left with a pointer to a memory address that is no longer valid. The rest of your program can, and probably does, exhibit signs of undefined behaviour, then.

Unless you show some more code, I suspect this will take care of the problem:

//change:
Pqueue_elem* newElems = realloc(q.elems, 4 * q.capacity * sizeof *newElems);
//to
q.elems = realloc(q.elems, 4 * q.capacity * sizeof *newElems);

Or better yet, check for NULL pointers:

Pqueue_elem* newElems = realloc(q.elems, 4 * q.capacity * sizeof *newElems);
if (newElems == NULL)
    exit( EXIT_FAILURE );// + fprintf(stderr, "Fatal error...");
q.elems = newElems;//<-- assign new pointer!

---

Looking at your pqueue_new function, I would suggest a different approach. Have it return the pointer to Pqueue. You're working with a piece of dynamic memory, treat it accordingly, and have your code reflect that all the way through:

Pqueue * pqueue_new(size_t size)
{//size_t makes more sense
    if (size < 4)
        size = 4;
    Pqueue* q = malloc(sizeof *q);
    check(q, "a new queue.");
    q->capacity = size;
    q->elems = malloc(q->capacity * sizeof *(q->elems));
    check(q->elems, "queue's elements");

    return q;
}

Alternatively, pass the function a pointer to a stack variable:

void pqueue_new(Pqueue *q, size_t size)
{
    if (q == NULL)
    {
        fprintf(stderr, "pqueue_new does not do NULL pointers, I'm not Chuck Norris");
        return;//or exit
    }
    if (size < 4)
        size = 4;
    check(q, "a new queue.");
    q->capacity = size;
    q->elems = malloc(q->capacity * sizeof *(q->elems));
    check(q->elems, "queue's elements");
}
//call like so:
int main ( void )
{
    Pqueue q;
    pqueue_new(&q, 3);
}

Those would be the more common approaches.

Answer 2

Thank you all for the suggestions! I wouldn't have solved it without them,

The strange behaviour was caused by an off by one error. I was reallocating the queue only when q->size >= q->capacity, but since q was indexed from 0, it meant that before realloc I was writing in a forbidden location (q->elems[q->size]), which messed everything up.