novice realloc question

[mordac]

Hi, writing a heap ADT, need to handle insertion into the heap when it
is full. Attempting to use realloc to do this, but realloc is changing
the contents of my heap! The following is my incHeapSize function,
which is supposed to increase the malloced space for an integer array
by 1:

Heap incHeapSize(Heap aHeap) {
int* tempHeap;
aHeap->maxSize++;
tempHeap = realloc(aHeap->heapArray, aHeap->maxSize);
if(tempHeap == NULL)
printf("incHeapSize() error: realloc failed.\n");
return aHeap;
}
aHeap->heapArray = tempHeap;
return aHeap;
}

Since aHeap->heapArray points to an integer array, I would expect that
realloc takes the integer array and mallocs space for 1 more integer,
then copies the contents of the original array into the new one, with
the extra integer space holding 0. But after incHeapSize() is used,
the contents of the current heap change:

original integer array:
999 483 31 11 22 27 4 2 1
array after running incHeapSize:
999 483 33 0 22 27 4 2 1

Clearly I'm using realloc incorrectly. I guess I could copy the
contents of the current heap into the new bigger heap by hand, but
isnt realloc supposed to keep the current contents of the memory
segment intact?

Any suggestions?

mordac

 

[Bruno Desthuilliers]

Hi, writing a heap ADT, need to handle insertion into the heap when it
is full. Attempting to use realloc to do this, but realloc is changing
the contents of my heap! The following is my incHeapSize function,
which is supposed to increase the malloced space for an integer array
by 1:

If your need to realloc(), you 'd better realloc() a bigger block, or
you'll end up calling realloc() very frequently.


Ok, I guess that Heap looks like this :
typedef struct {
size_t maxSize;
int *heapArray;
} *Heap;

Note that it would have help if you had posted this part too...

Heap incHeapSize(Heap aHeap) {

int* tempHeap;
aHeap->maxSize++;

Are you sure that you realloc with the right new size ?

tempHeap = realloc(aHeap->heapArray, aHeap->maxSize);

try this instead :
size_t new_size = sizeof *tempHeap * aHeap->maxSize;
tempHeap = realloc(aHeap->heapArray, newSize);

if(tempHeap == NULL)

missing curly brace. I guess you didn't copy/paste your code ?
{

printf("incHeapSize() error: realloc failed.\n");

Use fprint(stderr, ...) for this.

/* return aHeap; you return it anyway */
aHeap->maxSize--; /* remember, realloc() failed */

}

else {
aHeap->heapArray = tempHeap;

must do it by yourself
aHeap->heapArray[aHeap->maxSize-1] = 0;
}

return aHeap;
}

Now how does the caller knows that something went wrong ?

Since aHeap->heapArray points to an integer array,

int array or int pointer ?-)

I would expect that
realloc takes the integer array and mallocs space for 1 more integer,
then copies the contents of the original array into the new one,

So far, it seems ok.

with
the extra integer space holding 0.

Nop ! It will have any possible value. You have to set it to 0 by yourself

But after incHeapSize() is used,
the contents of the current heap change:

original integer array:
999 483 31 11 22 27 4 2 1
array after running incHeapSize:
999 483 33 0 22 27 4 2 1

cf problem with size...

Clearly I'm using realloc incorrectly. I guess I could copy the
contents of the current heap into the new bigger heap by hand, but
isnt realloc supposed to keep the current contents of the memory
segment intact?

It is.

Any suggestions?

Other than correcting the size asked when realloc() ?
Why don't you return an error code ?

Ok, here's a proposal :

int incHeapSize(Heap aHeap)
{
int result = 0;
int* array;
size_t new_size = sizeof *array * aHeap->maxSize + 1;

array = realloc((void *)aHeap->heapArray, new_size);
if (NULL == array)
{
fprintf(stderr
,"%s :: %d : incHeapSize() error: realloc() failed.\n"
,__FILE__
,__LINE__
);
result = 1;
}
else
{
array[aHeap->maxSize] = 0;
aHeap->heapArray = array;
aHeap->maxSize++;
}

return result;
}

Now you should consider increasing your heap size by blocks instead...

HTH
Bruno

 

[Al Bowers]

Hi, writing a heap ADT, need to handle insertion into the heap when it
is full. Attempting to use realloc to do this, but realloc is changing
the contents of my heap! The following is my incHeapSize function,
which is supposed to increase the malloced space for an integer array
by 1:

Heap incHeapSize(Heap aHeap) {
int* tempHeap;
aHeap->maxSize++;
tempHeap = realloc(aHeap->heapArray, aHeap->maxSize);
if(tempHeap == NULL)
printf("incHeapSize() error: realloc failed.\n");
return aHeap;
}
aHeap->heapArray = tempHeap;
return aHeap;
}

Since aHeap->heapArray points to an integer array, I would expect that
realloc takes the integer array and mallocs space for 1 more integer,
then copies the contents of the original array into the new one, with
the extra integer space holding 0. But after incHeapSize() is used,
the contents of the current heap change:

original integer array:
999 483 31 11 22 27 4 2 1
array after running incHeapSize:
999 483 33 0 22 27 4 2 1

Clearly I'm using realloc incorrectly.

Yes, you apparently are not allocating the correct size.
Try,

tempHeap = realloc(aHeap->heapArray,
(sizeof *tempArray) * aHeap->maxSize);

Also, There is a minor bug. You are incrementing maxSize before
you do the allocation. IF the allocation fails, the value of
maxSize will be inaccurate.

Here is an example:

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

typedef struct Heap
{
size_t maxSize;
int *heapArray;
} Heap,*pHeap;

pHeap incHeapSize(pHeap aHeap, int value) ;
void PrintHeap(pHeap aHeap);
void FreeHeap(pHeap aHeap);

int main(void)
{
Heap myHeap = { 0, NULL};

incHeapSize(&myHeap,999);
incHeapSize(&myHeap,483);
incHeapSize(&myHeap,31);
incHeapSize(&myHeap,11);
incHeapSize(&myHeap,22);
incHeapSize(&myHeap,27);
incHeapSize(&myHeap,4);
incHeapSize(&myHeap,2);
incHeapSize(&myHeap,1);

PrintHeap(&myHeap);
FreeHeap(&myHeap);
return 0;
}

pHeap incHeapSize(pHeap aHeap, int value)
{
int* tempHeap;

tempHeap = realloc(aHeap->heapArray,
(sizeof *tempHeap)*(aHeap->maxSize+1));
if(tempHeap == NULL)
{
printf("incHeapSize() error: realloc failed.\n");
return NULL;
}
aHeap->heapArray = tempHeap;
aHeap->heapArray[aHeap->maxSize++] = value;
return aHeap;
}

void PrintHeap(pHeap aHeap)
{
size_t i;

for(i = 0; i < aHeap->maxSize; i++)
{
printf("%d ",aHeap->heapArray);
if(i != 0 && i%5 == 0) putchar('\n');
}
putchar('\n');
return;
}

void FreeHeap(pHeap aHeap)
{
aHeap->maxSize = 0;
free(aHeap->heapArray);
aHeap->heapArray = NULL;
return;
}

 

[Bruno Desthuilliers]

(snip)

Also, There is a minor bug. You are incrementing maxSize before
you do the allocation. IF the allocation fails, the value of
maxSize will be inaccurate.

Here is an example:
(snip)

pHeap incHeapSize(pHeap aHeap, int value)
{
int* tempHeap;

tempHeap = realloc(aHeap->heapArray,
(sizeof *tempHeap)*(aHeap->maxSize+1));
if(tempHeap == NULL)
{
printf("incHeapSize() error: realloc failed.\n");
return NULL;
}
aHeap->heapArray = tempHeap;
aHeap->heapArray[aHeap->maxSize++] = value;
return aHeap;
}

And, err... how does the caller knows if incHeapSize() succeeded or
failed ?-)

Bruno

 

[Al Bowers]

(snip)


Also, There is a minor bug. You are incrementing maxSize before
you do the allocation. IF the allocation fails, the value of
maxSize will be inaccurate.

Here is an example:
(snip)

pHeap incHeapSize(pHeap aHeap, int value)
{
int* tempHeap;

tempHeap = realloc(aHeap->heapArray,
(sizeof *tempHeap)*(aHeap->maxSize+1));
if(tempHeap == NULL)
{
printf("incHeapSize() error: realloc failed.\n");
return NULL;
}
aHeap->heapArray = tempHeap;
aHeap->heapArray[aHeap->maxSize++] = value;
return aHeap;
}

And, err... how does the caller knows if incHeapSize() succeeded or
failed ?-)

The function will return a value representing the pointer to the
struct object if a successful reallocation. It will return NULL should
the reallocation fail. The caller can test the return value for
NULL.

 

[Bruno Desthuilliers]

(snip)


Also, There is a minor bug. You are incrementing maxSize before
you do the allocation. IF the allocation fails, the value of
maxSize will be inaccurate.

Here is an example:
(snip)

pHeap incHeapSize(pHeap aHeap, int value)
{
int* tempHeap;

tempHeap = realloc(aHeap->heapArray,
(sizeof *tempHeap)*(aHeap->maxSize+1));
if(tempHeap == NULL)
{
printf("incHeapSize() error: realloc failed.\n");
return NULL;
}
aHeap->heapArray = tempHeap;
aHeap->heapArray[aHeap->maxSize++] = value;
return aHeap;
}

And, err... how does the caller knows if incHeapSize() succeeded or
failed ?-)

The function will return a value representing the pointer to the
struct object if a successful reallocation. It will return NULL should
the reallocation fail. The caller can test the return value for
NULL.

Nop ! What is reallocated is a *member* of the Heap struct pointed to,
and if realloc() fails, then this member is unchanged. And as the Heap
pointer itself is unchanged, I can't see any reason for the function to
return it.

Bruno

 

[mordac]

If your need to realloc(), you 'd better realloc() a bigger block, or

you'll end up calling realloc() very frequently.

Agreed. Was increasing it by 1 for initial attempt.

Note that it would have help if you had posted this part too...
Okay.

try this instead :
size_t new_size = sizeof *tempHeap * aHeap->maxSize;
tempHeap = realloc(aHeap->heapArray, newSize);

I really should have scoured the newsgroup harder before I started
mouthing off questions like this. Theres a realloc primer on here that
helped a lot. However, your example below is more intuitive and
helpful anyway, so thanks.

missing curly brace. I guess you didn't copy/paste your code ?
{

Yeah, copied it by hand. Xemacs wouldn't copy outside of itself.
Forgot to use KClipper, but thats off topic..

fprintf(stderr
,"%s :: %d : incHeapSize() error: realloc() failed.\n"
,__FILE__
,__LINE__
);

Are __FILE__ and __LINE__ predefined macros in ANSI C? Thanks for the
idea.

Now you should consider increasing your heap size by blocks instead...

Yes yes, that I realize. Increasing by one was just to see if my
actions would break everything, which it did.

HTH
Bruno

Thanks Bruce

 

[Bertrand Mollinier Toublet]

Al Bowers wrote:



(snip)


Also, There is a minor bug. You are incrementing maxSize before
you do the allocation. IF the allocation fails, the value of
maxSize will be inaccurate.

Here is an example:

(snip)

pHeap incHeapSize(pHeap aHeap, int value)
{
int* tempHeap;

tempHeap = realloc(aHeap->heapArray,
(sizeof *tempHeap)*(aHeap->maxSize+1));
if(tempHeap == NULL)
{
printf("incHeapSize() error: realloc failed.\n");
return NULL;
}
aHeap->heapArray = tempHeap;
aHeap->heapArray[aHeap->maxSize++] = value;
return aHeap;
}


And, err... how does the caller knows if incHeapSize() succeeded or
failed ?-)

The function will return a value representing the pointer to the
struct object if a successful reallocation. It will return NULL should
the reallocation fail. The caller can test the return value for
NULL.

Nop ! What is reallocated is a *member* of the Heap struct pointed to,
and if realloc() fails, then this member is unchanged. And as the Heap
pointer itself is unchanged, I can't see any reason for the function to
return it.

Bruno, you can't see it because you did not look hard enough. Hint:
arguably, Al breaks an untouchable rule of structured coding by having
more than one return point in his code
It also took me a minute to see it, but to see Al persist after your
pointing out the "obvious" prompted me to look harder...

 

[Bruno Desthuilliers]

mordac wrote:

(snip)
BTW (and somewhat OT) : this 'tempHeap' identifier name is somewhat
misleading IMHO, since it's not a Heap but an int *. I guess this
confused Al Bowers in thinking incHeapSize() would return NULL on failure.

(snip the rest)

Bruno

 

[Bruno Desthuilliers]

Bruno, you can't see it because you did not look hard enough. Hint:
arguably, Al breaks an untouchable rule of structured coding by having
more than one return point in his code

woops ! Thanks, I see it now.

It also took me a minute to see it, but to see Al persist after your
pointing out the "obvious" prompted me to look harder...

Yeps. I guessed I've also been misleaded by the fact that the OP's code
also returned at the same point... but then it returned the Heap !-).

<Al>
Sorry, I'll put my glasses on next time (and no, I wont start a style
war about multiple exit points in a function <g>).
</Al>