freeing memory in recursion

the program makes a lot of recursive calls, so i need to free the memo

Page 1 of 1

13 Replies - 3105 Views - Last Post: 14 November 2009 - 01:51 PM Rate Topic: -----

#1 XerxesOfPersia  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 19
  • Joined: 16-May 09

freeing memory in recursion

Posted 12 November 2009 - 11:47 PM

ok for a class I'm forced to learn C. i know mostly java, so the memory freeing is new to me. here is the code...
this is a heap sort function intended to sort over 1,000 elements in an array. so far it crashes at 10,000 due to segmentation fault or bus error(shown in code).
#include <stdio.h>
#include <stdlib.h>
//#include <stddef.h>

void swap(void* ap, void* bp, size_t s){
	 int temp;
	 temp = *(int*)ap;
	 *(int*)ap = *(int*)bp;
	 *(int*)bp = temp;
}

int compar(void* ap, void* bp){
   if(*(int*)ap < *(int*)bp){
		return -5;			 
   }
   else if(*(int*)ap > *(int*)bp){
		return 5;	 
   }
	return 0;
}

void printarray(void* root, size_t nelem){
	int i;  
	for(i = 0; i < nelem; ++i){
			printf(" %i ", *(int*)(root + 4*i));		
	}
	printf("\n\n");	
}

void shiftdown(void* root, void* base, size_t nelem, size_t size){
	 
	 void* left = malloc(sizeof(void));
	 void* right = malloc(sizeof(void));
	 left = ((base - root)/size * 2 + 1)*size + root;
	 right = ((base - root)/size * 2 + 2)*size + root;
	 
	if(right <= root + size * (nelem - 1)){
			if(compar(right, base) > 0){
							 if(compar(left, right) > 0){
							 swap(base, left, size);
							 //free(right);//causes bus error
							 shiftdown(root, left, nelem, size);
							 //return;//doesn't matter??
							 }
							 else{
								swap(base, right, size);
								//free(left);//causes bus error
								shiftdown(root, right, nelem, size);
								//return;//doesn't matter??	  
							 }
			}		   
	 }
	 if(left <= root + size * (nelem - 1)){
			if(compar(left, base) > 0){
							swap(base, left, size);
							//free(right);//causes bus error
							shiftdown(root, left, nelem, size);	  
			}
	 }
	 //free(left);//causes segmentation fault
	 
	 //free(right);//causes segmentation fault
	 return;
	 
}

void heapify(void* root, void* base, size_t nelem, size_t size){
	 int heap;
	 heap = 1;
	 void* left = malloc(sizeof(void));
	 void* right = malloc(sizeof(void));
	 
	 left = ((base - root)/size * 2 + 1)*size + root;
	 right = ((base - root)/size * 2 + 2)*size + root;
	 
	 if(right <= root + size * (nelem - 1)){
			if(compar(right, base) > 0){
							 swap(base, right, size);
							 heap = 0;
			}		   
	 }
	 if(left <= root + size * (nelem - 1)){
			if(compar(left, base) > 0){
							swap(base, left, size);
							heap = 0;	   
			}
	 }
	 //free(left);//causes segmentation fault
	 //free(right);//causes segmentation fault
	 if(base < root + size * (nelem - 1))
	 heapify(root, base + 4,nelem, size);
	 
	 if(heap == 0)
	 heapify(root, root, nelem, size);
	 
 
	return; 
}

void srtheap(void* base, size_t nelem, size_t size){
	 void* root = malloc(sizeof(void));
	 root = base;
	 heapify(base, base, nelem, size);
	 while(nelem > 1){
		  swap(base, base + (nelem-1) * size, size);
		  nelem--;
		  shiftdown(root,base,nelem,size);
		  
	 }
	 
	 
}

int main(int argc, char *argv[])
{
	int a[1000];//works find until it goes to 10,000 segmentation fault
	int i;
	for( i = 0; i < 1000;i++){//works find until it goes to 10,000 segmentation fault
		 a[i] = i;	 
	}
	size_t size = 4;
	size_t nelem = sizeof(a)/sizeof(a[0]);
	void* base = malloc(sizeof(void));
	base = (void*)a;
	printarray(base, nelem);
	
	
	srtheap(base, nelem, size);
 
	printarray(base, nelem);
	//system("PAUSE");
	return 0;
}




there are comments on the places where i got errors. any help would be greatly appreciated.
if it makes any difference, i have been running this using secure shell on a linux or unix or something.
I'm not sure how and where to free the memory...

Is This A Good Question/Topic? 0
  • +

Replies To: freeing memory in recursion

#2 hackterr  Icon User is offline

  • D.I.C Regular

Reputation: 21
  • View blog
  • Posts: 293
  • Joined: 13-August 09

Re: freeing memory in recursion

Posted 13 November 2009 - 12:01 AM

Memory overload is a common symptom of recursion
there is no workaround for it unless you use an iterative loop instead of recursion
you will have to retain the stack while your recursion is in process.
Work through your program
if you see any of the values that are being uselessly stored till the end of the process delete them using "delete"

This post has been edited by hackterr: 13 November 2009 - 12:02 AM

Was This Post Helpful? 0
  • +
  • -

#3 XerxesOfPersia  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 19
  • Joined: 16-May 09

Re: freeing memory in recursion

Posted 13 November 2009 - 12:08 AM

View Posthackterr, on 12 Nov, 2009 - 11:01 PM, said:

if you see any of the values that are being uselessly stored till the end of the process delete them using "delete"


would "delete" work in C, if so how would i implement that?
the comments with free in it are the memory(s) that are no longer needed.
Was This Post Helpful? 0
  • +
  • -

#4 hackterr  Icon User is offline

  • D.I.C Regular

Reputation: 21
  • View blog
  • Posts: 293
  • Joined: 13-August 09

Re: freeing memory in recursion

Posted 13 November 2009 - 01:45 AM

use "free" for c
Was This Post Helpful? 0
  • +
  • -

#5 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5822
  • View blog
  • Posts: 12,675
  • Joined: 16-October 07

Re: freeing memory in recursion

Posted 13 November 2009 - 06:40 AM

What on earth is the point of all the void pointers? It's not like you're getting any use out of them; you're constantly casting the things. You're also using malloc and leaking all over the place.

e.g.
void* base = malloc(sizeof(void));
base = (void*)a; // you just lost the memory you were just pointing to, leak

void* left = malloc(sizeof(void));
left = ((base - root)/size * 2 + 1)*size + root;
// lost again



And about those mallocs; "sizeof(void)"? Know that, sizeof(void)!=sizeof(int). That's rather moot; your program shouldn't require any mallocs; at all.

Try getting rid of all the void * and malloc and go fro there.
Was This Post Helpful? 1
  • +
  • -

#6 XerxesOfPersia  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 19
  • Joined: 16-May 09

Re: freeing memory in recursion

Posted 13 November 2009 - 10:21 PM

View Postbaavgai, on 13 Nov, 2009 - 05:40 AM, said:

What on earth is the point of all the void pointers? It's not like you're getting any use out of them; you're constantly casting the things. You're also using malloc and leaking all over the place.


sorry about the void pointers, I just used this code to test my logic on the heap sort. my project is basically sort a lot ints, doubles, or floats which the user enters as inputs. It's pretty confusing...I have to upload my files into the afs system, then type in the "gcc -std=c99 -DRAND -DPRNT -DTYPE=float -DHEAP *.c" to compile the program and then "./a.out" to run the program. here i'll give you the exact code i used...

heapsort class
/*
 *
 *  srtheap.c file
 *
 */

#include <stdlib.h>
#include <string.h>
#include "srt.h"
#include <stdio.h>


void shiftdown(void* root, void* base, size_t nelem, size_t size, int (*compar)(const void *, const void *)){
	 
	 void* left = malloc(sizeof(void));
	 void* right = malloc(sizeof(void));
	 //void* parent = malloc(sizeof(void));
	 left = ((base - root)/size * 2 + 1)*size + root;
	 right = ((base - root)/size * 2 + 2)*size + root;
	 //parent = ((base - root)/size - 1) / 2 * size + root;
	 
	if(right <= root + size * (nelem - 1)){
			if(compar(right, base) > 0){
							 if(compar(left, right) > 0){
							 swap(base, left, size);
							 free(right);
							 shiftdown(root, left, nelem, size,compar);
							 return;
							 }
							 else{
								swap(base, right, size);
								free(left);
								shiftdown(root, right, nelem, size,compar);
								return;	  
							 }
			}		   
	 }
	 if(left <= root + size * (nelem - 1)){
			if(compar(left, base) > 0){
							swap(base, left, size);
							free(right);
							shiftdown(root, left, nelem, size,compar);
								  
			}
	 }
	 //free(left);
	 
	 //free(right);
	 return;
	 
}

void heapify(void* root, void* base, size_t nelem, size_t size, int (*compar)(const void *, const void *)){
	 
	 int heap;
	 heap = 1;
	 void* left = malloc(sizeof(void));
	 void* right = malloc(sizeof(void));
	 
	 left = ((base - root)/size * 2 + 1)*size + root;
	 right = ((base - root)/size * 2 + 2)*size + root;
	 
	 if(right <= root + size * (nelem - 1)){
			if(compar(right, base) > 0){
							 swap(base, right, size);
							 heap = 0;
			}		   
	 }
	 if(left <= root + size * (nelem - 1)){
			if(compar(left, base) > 0){
							swap(base, left, size);
							heap = 0;	   
			}
	 }
	 
	 free(left);
	 free(right);
	 
	 if(base < root + size * (nelem - 1))
	 heapify(root, base + size,nelem, size,compar);
	 
	 if(heap == 0)
	 heapify(root, root, nelem, size,compar);
	 
 
	return; 
}

void srtheap(void* base, size_t nelem, size_t size, int (*compar)(const void *, const void *)){
	 void* root = malloc(sizeof(void));
	 root = base;
	 heapify(base, base, nelem, size, compar);
	 while(nelem > 1){
		  swap(base, base + (nelem-1) * size, size);
		  nelem--;
		  shiftdown(root,base,nelem,size,compar);
		  
	 }
	 
	 
}



the main class...this was given to us and CANNOT be changed, I don't really know how it works, but it does.

/*
 *
 *  main.c file
 *
 */

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include "srt.h"

int compare(const void *, const void *);

int main(int argc, char *argv[]) {

	int size = argc == 2 ? atoi(argv[1]) : SHRT_MAX;

	TYPE *a = calloc(size, sizeof(TYPE));

#ifdef RAND
	for (int i = 0; i < size; ++i) {

		a[i] = (TYPE)rand() / RAND_MAX;
	}
#else
	for (int i = 0; i < size; ++i) {

		a[i] = i;
	}
#endif

#if defined BUBB
	srtbubb(a, size, sizeof(TYPE), compare);
#elif defined HEAP
	srtheap(a, size, sizeof(TYPE), compare);
#elif defined INSR
	srtinsr(a, size, sizeof(TYPE), compare);
#elif defined MERG
	srtmerg(a, size, sizeof(TYPE), compare);
#else
	qsort(a, size, sizeof(TYPE), compare);
#endif

#ifdef PRNT
	for (int i = 0; i < size; ++i) {

		printf("%f\n", a[i]);
	}
#else
	for (int i = 0; i < size - 1; ++i) {

		if (a[i] > a[i + 1]) {

			printf("fail\n");
			goto end;
		}
	}

	printf("pass\n");
#endif

end:

	free(a);

	return 0;
}

int compare(const void *p1, const void *p2) {

	if (*(TYPE *)p1 < *(TYPE *)p2) {

		return -5;
	}
	else if (*(TYPE *)p1 > *(TYPE *)p2) {

		return +5;
	}

	return 0;
}



the point is I have to use void pointers, because i dont know what the size of the type is and he specifically said I have to use them. All I need is how to free the memory. the code for all the other methods were given...
Was This Post Helpful? 0
  • +
  • -

#7 rs4  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 29
  • View blog
  • Posts: 153
  • Joined: 01-February 09

Re: freeing memory in recursion

Posted 13 November 2009 - 11:54 PM

As baavgai said you don't need to impliment your void pointers with a vaule, so go through all your code and change

void* name = malloc(sizeof(void));//this wastes memory and does nothing

to

void* name;

I am not certian how your code works but you could try change some void pointers could be changed to globals, if there value never change, or they only ever require one value at a time.
Was This Post Helpful? 0
  • +
  • -

#8 XerxesOfPersia  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 19
  • Joined: 16-May 09

Re: freeing memory in recursion

Posted 14 November 2009 - 12:01 AM

My view on malloc was iffy at the beginning, but I did take out the four malloc lines and it still complains about a segmentation fault here is my new code to workl with...

/*
 *
 *  srtheap.c file
 *
 */

#include <stdlib.h>
#include <string.h>
#include "srt.h"
#include <stdio.h>


void shiftdown(void* root, void* base, size_t nelem, size_t size, int (*compar)(const void *, const void *)){
	 int leftIndex = ((base - root)/size * 2 + 1);
	 int rightIndex = ((base - root)/size * 2 + 2);
	 void* left;// = malloc(sizeof(void));
	 void* right;// = malloc(sizeof(void));
	 
	 
	 
	 if(leftIndex < nelem){
				  left = leftIndex*size + root;
	 }
	 if(rightIndex < nelem){
				   right = rightIndex*size + root;
	 }
	if(rightIndex < nelem){
			if(compar(right, base) > 0){
							 if(compar(left, right) > 0){
							 swap(base, left, size);
							 //free(right);//causes bus error
							 shiftdown(root, left, nelem, size, compar);
							 //return;//doesn't matter??
							 }
							 else{
								swap(base, right, size);
								//free(left);//causes bus error
								shiftdown(root, right, nelem, size, compar);
								//return;//doesn't matter??	  
							 }
			}		   
	 }
	 if(leftIndex < nelem){
			if(compar(left, base) > 0){
							swap(base, left, size);
							//free(right);//causes bus error
							shiftdown(root, left, nelem, size, compar);	  
			}
	 }
	 //free(left);//causes segmentation fault
	 
	 //free(right);//causes segmentation fault
	 free(base);
	 free(root);
	 free(compar);
	 return;
}

void heapify(void* root, void* base, size_t nelem, size_t size, int (*compar)(const void *, const void *)){
	 
	 int heap;
	 heap = 1;
	 int baseIndex = (base - root)/size;
	 int leftIndex = ((base - root)/size * 2 + 1);
	 int rightIndex = ((base - root)/size * 2 + 2);
	 
	 void* left;// = malloc(sizeof(void));
	 void* right;// = malloc(sizeof(void));
	 
	 if(leftIndex < nelem)
	 left = root + leftIndex*size;
	 if(rightIndex < nelem)
	 right = root + rightIndex*size;
	 
	 if(rightIndex < nelem){
			if(compar(right, base) > 0){
							 swap(base, right, size);
							 heap = 0;
			}		   
	 }
	 if(leftIndex < nelem){
			if(compar(left, base) > 0){
							swap(base, left, size);
							heap = 0;	   
			}
	 }
	 
	 //free(left);
	 //free(right);
	 
	 if(baseIndex + 1 < nelem)
	 heapify(root, base + size,nelem, size,compar);
	 
	 if(heap == 0)
	 heapify(root, root, nelem, size,compar);
	 
	 free(base);
	 free(root);
	 free(compar);
	return; 
}

void srtheap(void* base, size_t nelem, size_t size, int (*compar)(const void *, const void *)){
	 printf("hello");
	 void* root = malloc(sizeof(void));
	 root = base;
	 heapify(base, base, nelem, size, compar);
	 while(nelem > 1){
		  swap(base, base + (nelem-1) * size, size);
		  nelem--;
		  shiftdown(root,base,nelem,size,compar);
		  
	 }
	 
	 
}




I added a couple if statements to check if the pointers were out of bounds and I should printout "hello", but the segmentaion fault happens before it?!?!? what is a segmentation fault?
Was This Post Helpful? 0
  • +
  • -

#9 XerxesOfPersia  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 19
  • Joined: 16-May 09

Re: freeing memory in recursion

Posted 14 November 2009 - 01:28 AM

also can a segmentation fault be caused by a stack overflow?, because the program works with 6000 elements in the array, but not 6500 or 32000
if so, how would I fix that?
Was This Post Helpful? 0
  • +
  • -

#10 rs4  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 29
  • View blog
  • Posts: 153
  • Joined: 01-February 09

Re: freeing memory in recursion

Posted 14 November 2009 - 03:31 AM

Quote

Also can a segmentation fault be caused by a stack overflow?


Google is your friend,
found this on this site Cprogramming,

Quote

A fifth way of causing a segfault is a recursive function that uses all of the stack space. On some systems, this will cause a "stack overflow" report, and on others, it will merely appear as another type of segmentation fault.

So yes would be your answer to that. What can you do ...

1. If you can make your code non-recursive i.e use loops it will be able to handle a infinite sized sort
2. Anything that is going to be a constant value, make it a global
3. If you still want more space be inventive set up arrays using malloc and realloc and create and expand global arrays to store data, give each recursion an number start at 0 and add one each time then get the related item out of the global array.

Other people probaly will have better ideas I can't say I've dealt with much recursive programing.

This post has been edited by rs4: 14 November 2009 - 03:32 AM

Was This Post Helpful? 0
  • +
  • -

#11 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5822
  • View blog
  • Posts: 12,675
  • Joined: 16-October 07

Re: freeing memory in recursion

Posted 14 November 2009 - 09:21 AM

Wow. So, your instructor is into C and hates you? :P

The point of this pain, um exercise, is to make reusable code. To that end you have a function sig that passes "sizeof(TYPE)" to the sorts, implying the sort doesn't have access to TYPE at runtime. In this way, all the sorts should work on any type. If this is unclear from what you've been given, that's unsurprising.

Note that as the main stands, it only works with float.
a[i] = (TYPE)rand() / RAND_MAX;
printf("%f\n", a[i]);



For extra fun, you've been give a compare, but no swap in main. If it were there, it would look like this:
void swap(void *p1, void *p2) {
	TYPE temp = *(TYPE *)p1;
	*(TYPE *)p1 = *(TYPE *)p2;
	*(TYPE *)p2 = temp;
}



So, I was wrong about malloc; you'll need just one, for the swap. I'm not even going the deal with the heap sort. It's a convoluted sort in its own right and your considerations just make it worse. Rather, I want to write the bubble sort for you. From that, you might be able to get some ideas.

#include <stdlib.h>
#include <string.h>
#include "srt.h"

// compile with
// gcc -std=c99 -DRAND -DPRNT -DTYPE=float -DBUBB *.c

// this should be in "srt.h"
// writing the whole function pointer syntax out is absurd
typedef int (*Compare)(const void *, const void *);

// this is our local swap.
// in addition to p1 and p2, it needs to have a scratch buffer and a size
static void swap(void *p1, void *p2, void *temp, size_t elementSize) {
	memcpy(temp, p1, elementSize);
	memcpy(p1, p2, elementSize);
	memcpy(p2, temp, elementSize);
}

// this is a standard bubble sort
void srtbubb(void *a, int size, size_t elementSize, Compare cmp){
	void *temp = malloc(elementSize); // prepare a temporary buffer
	int swapped = 1; // in old C, 0 and 1 for bool.  since you're using C99, you could use bool with stdbool.h
	while(swapped) { // keep going until you've made it through the whole list with no swaps
		void *p = a; // use a pointer to point to the first element
		int i; // for the loop
		
		swapped = 0; // reset flag, no swaps yet
		for(i=0; i<size-1; i++) { // not, it's one less the size of the list, the last can't swap with the one after
			// use the compare we were given
			if (cmp(p, p+elementSize)>0) { // the next element is a the position elementSize after the current
				swap(p, p+elementSize, temp, elementSize); // call the swap
				swapped = 1; // note that we've swapped
			}
			p += elementSize; // move to the next element
		}
		size--; // small optimization, last value should be in correct position
	}
	free(temp); // free our memory
}



Hope this helps.
Was This Post Helpful? 1
  • +
  • -

#12 XerxesOfPersia  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 19
  • Joined: 16-May 09

Re: freeing memory in recursion

Posted 14 November 2009 - 10:53 AM

hmmmmm, I think i'm going to try and make my recursive methods, shiftdown and heapify, non resursive using loops. and I could probably make some variables global too. Thanks for the help :D , I'll keep you guys posted!

oh the sorry but the swap function, it is in the following header file and i can only change what is in the srtheap (class)

/*
 *
 *  after splitting this file into the five source files:
 *
 *	srt.h, main.c, srtbubb.c, srtinsr.c, srtmerg.c
 *
 *  compile using the command:
 *
 *	gcc -std=c99 -DRAND -DPRNT -DTYPE=float -D{BUBB, HEAP, INSR, MERG} *.c
 *
 */

/*
 *
 *  srt.h file
 *
 */

#ifndef SRT_H
#define SRT_H

#include <string.h>

#define MAX_BUF 256

#define swap(qx,qy,sz)											  \
do {																\
	char buf[MAX_BUF];											  \
	char *q1 = qx;												  \
	char *q2 = qy;												  \
	for (size_t m, ms = sz; ms > 0; ms -= m, q1 += m, q2 += m) {	\
		m = ms < sizeof(buf) ? ms : sizeof(buf);					\
		memcpy(buf, q1, m);										 \
		memcpy(q1, q2, m);										  \
		memcpy(q2, buf, m);										 \
	}															   \
} while (0)

void srtbubb(void *, size_t, size_t, int (*)(const void *, const void *));
void srtheap(void *, size_t, size_t, int (*)(const void *, const void *));
void srtinsr(void *, size_t, size_t, int (*)(const void *, const void *));
void srtmerg(void *, size_t, size_t, int (*)(const void *, const void *));

#endif /* SRT_H */


Was This Post Helpful? 0
  • +
  • -

#13 XerxesOfPersia  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 19
  • Joined: 16-May 09

Re: freeing memory in recursion

Posted 14 November 2009 - 12:43 PM

I think i narrowed down my error to the heapify method. I went back to the very first code i gave you and modified the array size and initialization so that it makes the elements in decreasing order, thus making it a heap. so in the srtheap method there is no need to heapify. the program instead of crashing at a little over 6000 elements it works with 34000 elements :D . I think the problem is my heapify method, I admit, is rather inefficient. Any suggestions to making the heapify method more efficient?

oh here is the code that i got working with 34,000 elements.

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

void swap(void* ap, void* bp, size_t s){
	 int temp;
	 temp = *(int*)ap;
	 *(int*)ap = *(int*)bp;
	 *(int*)bp = temp;
}

int compar(void* ap, void* bp){
   if(*(int*)ap < *(int*)bp){
		return -5;			 
   }
   else if(*(int*)ap > *(int*)bp){
		return 5;	 
   }
	return 0;
}

void printarray(void* root, size_t nelem){
	int i;  
	for(i = 0; i < nelem; ++i){
			printf(" %i ", *(int*)(root + 4*i));		
	}
	printf("\n\n");	
}

void shiftdown(void* root, void* base, size_t nelem, size_t size){
	 int leftIndex = ((base - root)/size * 2 + 1);
	 int rightIndex = ((base - root)/size * 2 + 2);
	 void* left;
	 void* right;
	 
	 
	 
	 if(leftIndex < nelem){
				  left = leftIndex*size + root;
	 }
	 if(rightIndex < nelem){
				   right = rightIndex*size + root;
	 }
	if(rightIndex < nelem){
			if(compar(right, base) > 0){
							 if(compar(left, right) > 0){
							 swap(base, left, size);
							 //free(right);//causes bus error
							 shiftdown(root, left, nelem, size);
							 //return;//doesn't matter??
							 }
							 else{
								swap(base, right, size);
								//free(left);//causes bus error
								shiftdown(root, right, nelem, size);
								//return;//doesn't matter??	  
							 }
			}		   
	 }
	 if(leftIndex < nelem){
			if(compar(left, base) > 0){
							swap(base, left, size);
							//free(right);//causes bus error
							shiftdown(root, left, nelem, size);	  
			}
	 }
	 //free(left);//causes segmentation fault
	 
	 //free(right);//causes segmentation fault
	 //free(base);
	 //free(root);
	 return;
	 
}

void heapify(void* root, void* base, size_t nelem, size_t size){//source of error: stack overflow error
	 int heap;
	 heap = 1;
	 int baseIndex = (base - root)/size;
	 int leftIndex = ((base - root)/size * 2 + 1);
	 int rightIndex = ((base - root)/size * 2 + 2);
	 
	 void* left;
	  
	 void* right;
	 
	 if(leftIndex < nelem)
	  left = leftIndex*size + root;
	  if(rightIndex < nelem)
	  right = rightIndex*size + root;
	 
	 //left = 
	 //right =
	 
	 if(rightIndex < nelem){
			if(compar(right, base) > 0){
							 swap(base, right, size);
							 heap = 0;
			}		   
	 }
	 if(leftIndex < nelem){
			if(compar(left, base) > 0){
							swap(base, left, size);
							heap = 0;	   
			}
	 }
	 
	 //free(left);
	 //free(right);
	 
	 if(baseIndex + 1 < nelem)
	 heapify(root, base + size,nelem, size);
	 
	 if(heap == 0)
	 heapify(root, root, nelem, size);
	 
	 //free(base);
	 //free(root);
	 
	return; 
}

void srtheap(void* base, size_t nelem, size_t size){
	 //left = malloc(sizeof(void));
	 //right =  malloc(sizeof(void));
	 //void* root = malloc(sizeof(void));
	 //root = base;
	 //heapify(base, base, nelem, size);//modified out because it is already a heap
	 while(nelem > 1){
		  swap(base, base + (nelem-1) * size, size);
		  nelem--;
		  shiftdown(base,base,nelem,size);
		  
	 }
	 
	 
}

int main(int argc, char *argv[])
{
	int SIZE = 34000;
	int a[SIZE];//works find until it goes to 10,000 segmentation fault
	int i;
	for( i = 0; i < SIZE;i++){//works find until it goes to 10,000 segmentation fault
		 a[i] = SIZE - i;	 
	}
	size_t size = 4;
	size_t nelem = sizeof(a)/sizeof(a[0]);
	void* base = malloc(sizeof(void));
	base = (void*)a;
	printarray(base, nelem);
	
	
	srtheap(base, nelem, size);
	
	//printf("%i\n",*(int*)(base+1001*4));
	printarray(base, nelem);
	printf("Sorted\n");
	system("PAUSE");
	return 0;
}



there is a lot of stuff commented out, those are just stuff I tried to no avail.

Thanks for your help! :D
Was This Post Helpful? 0
  • +
  • -

#14 XerxesOfPersia  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 19
  • Joined: 16-May 09

Re: freeing memory in recursion

Posted 14 November 2009 - 01:51 PM

vici!!!!!!!!!!!!!!! :D

The heapify method was extremly inefficient, so it would cause stackoverflow errors. I made the heapify method a lot more efficient and not recursive. now the program not only works for 32,000 elements, it works for 1,000,000+!!!!!!!

Thanks for are your help!!!!! :D
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1