435,635 Members | 2,227 Online
Need help? Post your question and get tips & solutions from a community of 435,635 IT Pros & Developers. It's quick & easy.

# novice realloc question

 P: n/a 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 Nov 14 '05 #1
9 Replies

 P: n/a 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 Nov 14 '05 #2

 P: n/a 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 #include 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/ Nov 14 '05 #3

 P: n/a 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 Nov 14 '05 #4

 P: n/a 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/ Nov 14 '05 #5

 P: n/a 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 Nov 14 '05 #6

 P: n/a > 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 Nov 14 '05 #7

 P: n/a 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 Nov 14 '05 #8

 P: n/a 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 Nov 14 '05 #9

 P: n/a 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 !-). Sorry, I'll put my glasses on next time (and no, I wont start a style war about multiple exit points in a function ). Nov 14 '05 #10

### This discussion thread is closed

Replies have been disabled for this discussion.