Double Free or Corruption error when re-sizing Priority Queue

Question

I've run into this error before, but the circumstances baffle me as I have run nearly this exact set of functions without having this issue.

Let me break it down:

The error is being caused by the resize() private member function of a custom priority queue I am working on. It is all centered around de-allocating the pointer to the old queue array. Before I explain any further, let me list the handful of relatively small functions I've isolated the problem to.

void unfairQ::enqueue(int val)
{
    if (isFull())
        resize();   

    numElements++;
    ageCount++;

    heapArr[numElements].data = val;
    heapArr[numElements].age = 1;
    heapArr[numElements].priority = heapArr[numElements].data;

    heapifyUp(numElements);

    if (ageCount == 100) {
        heapSort();
        ageCount = 0;
    }

    return;
}

bool unfairQ::isFull()
{
    return (numElements == capacity);
}

void unfairQ::resize()
{
    int newCap = (capacity * 1.5);
    queueNode *tempHeap = new queueNode[newCap];

    for (int i = 1; i <= numElements; i++) {
        tempHeap[i].data = heapArr[i].data;
        tempHeap[i].age = heapArr[i].age;
        tempHeap[i].priority = heapArr[i].priority;
    }
    // delete [] heapArr;
    capacity = newCap;
    heapArr = tempHeap;
    return;
}

The commented out line in the resize function is the one causing problems. If I do delete the pointer to the array I get the "double free" error, however if I remove that line I get a "free(): invalid next size (normal):" if I enqueue enough values to require a second resize().

Please let me know if you need any more information or if I need to clarify anything.

Answer 1

You seem to be using your array with indexes starting from 1, c++ uses indexes starting from 0. This can cause a buffer overflow.

For example:

If capacity is currently 5 (so heapArray can have 5 entries) andnumElementsis currently 4, yourisFullwill returnfalse(correctly), however yourenqueuecode then incrementsnumElements(from 4 to 5) and attempts to write toheapArray[5]` which is out of bounds and may overwrite some other memory.

Solution: start your indexes from 0, e.g. in the enqueue function, increment numElements after you write the data heapArray[numElements]

Answer 2

I found the problem, while I was referencing/incrementing/decrementing all the indices correctly and calling the appropriate functions at the appropriate times, I was operating under the notion that I was working with indices 1-size, but in the constructor (something I hadn't glanced at for a while) I'd initialized numElements as 0 which broke the whole gosh darned thing.

Fixed that and now everything is hunky dory!

Thanks for the help guys.