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 9 2323
mordac wrote: 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
mordac wrote: 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[i]);
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;
}
--
Al Bowers
Tampa, Fl USA
mailto: xa******@myrapidsys.com (remove the x to send email) http://www.geocities.com/abowers822/
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 ?-)
Bruno
Bruno Desthuilliers wrote: 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.
--
Al Bowers
Tampa, Fl USA
mailto: xa******@myrapidsys.com (remove the x to send email) http://www.geocities.com/abowers822/
Al Bowers wrote:
Bruno Desthuilliers wrote:
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
> 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. :) if(tempHeap == NULL) 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
Bruno Desthuilliers wrote: Al Bowers wrote:
Bruno Desthuilliers wrote:
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...
--
Bertrand Mollinier Toublet
Currently looking for employment in the San Francisco Bay Area http://www.bmt.dnsalias.org/employment
mordac wrote:
(snip) if(tempHeap == NULL)
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
Bertrand Mollinier Toublet wrote: Bruno Desthuilliers wrote:
Al Bowers wrote:
(snip) 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 :-)
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> This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Henrik J |
last post by:
Hello group...
I have this little problem:
I'm using a struct **foo. I have allocated x foo's using malloc:
foo=(FOO**)malloc(Amount*sizeof(FOO*));
No problem....!
|
by: Jonas |
last post by:
Hi,
I'm 99 % sure that Standard C guarantees to do a memory move inside
realloc() in case the new, returned memory block (address) is different than
the original one. Can any C expert confirm...
|
by: Walter Roberson |
last post by:
If realloc() finds it necessary to move the memory block, then
does it free() the previously allocated block?
The C89 standard has some reference to undefined behaviour if one
realloc()'s memory...
|
by: James S. Singleton |
last post by:
Thanks to everybody who provided an answer to my previous question on
this. I am trying to grasp the nitty-gritty details of this, and I am
having difficulties understanding some of the issues...
|
by: James Brown |
last post by:
Hi all,
I just wanted to make sure I understand realloc
void *realloc( void *memblock, size_t size );
1. when memblock is zero, realloc behaves like malloc
2. when memblock is non-zero, and...
|
by: Deephay |
last post by:
Greetings all,
I have a program that used the realloc() function to change the
allocated size of a buffer, the program works with some arguments, but
with some other arguments, it will show me...
|
by: banansol |
last post by:
Hi,
I just want to get this right.
A call to realloc() will return NULL on error and the original memory
is left untouched,
both when requesting a larger or a smaller size that the original,...
|
by: Kenneth Brody |
last post by:
I looked at my copy of n1124, and I didn't see anything about this
particular situation...
What happens if you realloc() to a size of zero?
Implementations are allowed to return NULL on...
|
by: Guillaume Dargaud |
last post by:
Hello all,
I have a 'good practice' question.
Lately I've been using a lot of functions such as this:
void Func(int Size, double *Array) {
static double *Transformed=NULL;...
|
by: isladogs |
last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM).
In this month's session, we are pleased to welcome back...
|
by: isladogs |
last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM).
In this month's session, we are pleased to welcome back...
|
by: Vimpel783 |
last post by:
Hello!
Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
|
by: jfyes |
last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
|
by: ArrayDB |
last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
|
by: PapaRatzi |
last post by:
Hello,
I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
|
by: Defcon1945 |
last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
|
by: Shællîpôpï 09 |
last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome former...
| |