Ex18 *bubble_sort function

C
#1

In the *bubble_sort function, the pointer ‘numbers’ is copied to the pointer ‘target’. The below code is copied from this function. I don’t understand why we can’t use *numbers which was passed to this function.
Why is it necessary to make a copy of it to another pointer (*target)?.

int target = malloc(countsizeof(int));
if(!ptr_target){
die(“Memory error1.”);
}
memcpy(target, numbers, count*sizeof(int));

I tried writing code using the pointer numbers, and it works only if I remove 'free(sorted) from the ‘test_sorting’ function. That make no sense to me either. Any insight on this would be appreciated.
Thanks,

#2

I guess the function doesn’t sort the input in place but creates a new sorted array. You can do bubble sort in place, but if after the call sorted doesn’t point to location on the heap, you can’t call free on it.

That’s what I’m guessing, you need to show more context if you want a definite answer.

If you wrap your code in code tags like so

[code]
# your code
[/code]

it doesn’t get garbled by the forum software.

#3

florian,
Thanks for the help. This is Ex 18 in "Learn C the Hard way. I modified the *ptr_bubble_sort function
to see if i could use the pointer *numbers in the function without creating the *ptr_target pointer.
(note: this is the same program that is in the book in ex18, I added “ptr_” to all the pointers so I could keep track of pointers and variables. The original code in the *ptr_bubble_sort function is included, but commented out.

If the program is run with > ex18 4 3 1 the output will be corrupted in the second call to bubble_sort. The first two integers will be corrupted. If you comment out the free(ptr_sorted) line in the test_sorting
function and rerun the program it will work. I am just curious as to why it fails if the memory is freed and does not fail if the memory is not freed.
Thanks,

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

/** Our old friend die from ex17 */
void die(const char *ptr_message)
{
	if(errno){
		perror(ptr_message);
	}else{
		printf("ERROR: %s\n", ptr_message);
	}
	exit(1);
}

// a typedef creates a fake type, in this case for a function pointer
typedef int(*ptr_compare_cb)(int a, int b);  // Create a dummy type called ptr_compare_cb

/**
* A classic bubble sort function that uses the ptr_compare_cb
* to do the sorting.
*/
int *ptr_bubble_sort(int *ptr_numbers, int count, ptr_compare_cb cmp)
{
	int temp = 0;
	int i = 0;
	int j = 0;
	
	//int *ptr_target = malloc(count*sizeof(int));  // allocate memory one int per number of entered integers on command line.
	                                           // point to it with *ptr_target

//if(!ptr_target){  // if ptr_target is null kill program
//	die("Memory error1.");
//}
	//memcpy(ptr_target, ptr_numbers, count*sizeof(int));  
	
/**	for(i=0; i<count; i++){
		for(j=0; j<count-1; j++){
			if(cmp(ptr_target[j], ptr_target[j+1]) > 0){
				temp = ptr_target[j+1];
				ptr_target[j+1] = ptr_target[j];
				ptr_target[j] = temp;
				
*/	printf(" address for *ptr_numbers = %p\n", &ptr_numbers);
	
	for(i=0; i<count; i++){
		for(j=0; j<count-1; j++){
			//printf(" ptr_numbers[j] = %d, ptr_numbers[j+1] = %d\n", ptr_numbers[j], ptr_numbers[j+1]);
			if(cmp(ptr_numbers[j], ptr_numbers[j+1]) > 0){
				temp = ptr_numbers[j+1];
				ptr_numbers[j+1] = ptr_numbers[j];
				ptr_numbers[j] = temp;
			}
		}
	}
	
	return ptr_numbers;
}

int sorted_order(int a, int b)
{
	return a-b;
}

int reverse_order(int a, int b)
{
	return b-a;
}	

int strange_order(int a, int b)
{
	if(a==0||b==0){
		return 0;
	}else{
		return a%b;
	}
}

/**
* Used to test that we are sorting things correctly
* by doing the sort and printing it out.
*/
void test_sorting(int *ptr_numbers, int count, ptr_compare_cb cmp)
{
	int i=0;
	
	for(i=0; i<count; i++){
		printf("TS1 numbers %d  i =  %d \n", ptr_numbers[i], i);
	}
	int *ptr_sorted = malloc(count*sizeof(int));
	ptr_sorted = ptr_bubble_sort(ptr_numbers, count, cmp);

	if(!ptr_sorted)
		die("Failed to sort as requested");
		
	printf("\n");

	free(ptr_sorted);
}
	
int main(int argc, char *argv[])
{
	if(argc<2) die("USAGE: Ex18 4 3 1 5 6");
	
	int count = argc - 1;
	int i = 0;
	char **ptr_inputs = argv +1;
	
	int *ptr_numbers = malloc(count*sizeof(int));
	if(!ptr_numbers) die("Memory error2.");
	
	for(i=0; i<count; i++){
		ptr_numbers[i] = atoi(ptr_inputs[i]);
	}
	
	test_sorting(ptr_numbers, count, sorted_order);
	test_sorting(ptr_numbers, count, reverse_order);
	test_sorting(ptr_numbers, count, strange_order);
	
	free(ptr_numbers);    //  **********  if this is commented out, the program works.  If it is not
// commented out, the first two numbers input will be corrupted.
	
	return 0;
}
#4

Apologies for the delay in getting back to you. I’ve had a busy week.

Okay, here’s two lines from your code in test_sorting, after the debug-for-loop:

int *ptr_sorted = malloc(count*sizeof(int));
ptr_sorted = ptr_bubble_sort(ptr_numbers, count, cmp);
  1. You allocate a new array on the heap and save the memory address in ptr_sorted.
  2. ptr_bubble_sort sorts the array pointed to by ptr_numbers and returns the same pointer, which you then assign to ptr_sorted. That means the array you allocated in the first step is forever lost because you have just overwritten the only place where its address was stored.
  3. A little later (the line you commented out) you free the memory pointed to by ptr_sorted, which is the array you originally allocated in main. Now this chunk of memory is fair game and there’s no knowing what may or may not happen there – including what data is stored when you try to sort it the second time.

As for the crash, the second time test_sorting is called, ptr_sorted (which, again, points to the array created in main) has already been freed by the first call, and a double-free is something most programs choke on.

Does this help?