17 replies to this topic

[Turk4n]

So, been working with pthreads and put up a concurrent quicksort program, thing is I am using only structs and now when I am trying to redesign with using malloc/calloc eiher would be fine.
I seem to not be able to work on the logic...

Is there any "tutorial" or sample code I could peek into that fills in the most basic information and understanding on how to apply it...

Thanks in advance...

[dargueta]

What're you trying to dynamically allocate? The data you're passing among the threads?

[Turk4n]

I am having a struct, and a struct carrier, the struct holds an int pointer and 2x ints. The carrier just handles it for passing around the struct for the quicksort function. I have tried some approaches but none of them "works" technically these approaches are not "used". As I still get stack overflow(due to I am only using the structs and not allocating them correctly in heap).

[dargueta]

You allocate a struct, then pass the pointer around, making sure you lock the struct before accessing it. For example:

MYSTRUCT *blah;

blah = malloc(sizeof *blah);

pthread_mutex_init(blah->lock, attrib stuff here);
blah->array = calloc(sizeof *blah->array, 1024);

(pass to some function)

pthread_mutex_destroy(blah->lock);
free(blah->array);
free(blah);

[Turk4n]

Okay, bear with me when I am feeling abit confused at this point. I will post how I done so far.

typedef struct {    
    int* array;
    int left;
    int right;
}quicksort_arguments;

quicksort_arguments quicksort_arguments_constructor ( int *array, int left, int right){
    /* DOES NOTHING !!!!!
        quicksort_arguments *qa = (quicksort_arguments*) malloc(SIZE*sizeof(quicksort_arguments));
        qa->array = array;
        qa->left = left;
        qa->right = right;
        return *qa;
    */
    quicksort_arguments qa;
    qa.array = array;
    qa.left = left;
    qa.right = right;
    return qa;
}

// Thread wrapper for quicksort//
void* quicksort_thread_function (void *args)
{
    quicksort_arguments *a = (quicksort_arguments *)args;
    quicksort (a->array, a->left, a->right);
    return NULL;
}

void quicksort (int *array, int left, int right){
    int i, last;
    pthread_t lt;
    //
    quicksort_arguments qa;
    //Reference handling
    quicksort_arguments *qb = &qa;
    
    if (left >= right)
        return;
    
    swap (array, left, average(left, right));
    last = left;
    
    for (i = left + 1; i <= right; i++) {
        
        if (array[i] < array[left] ) {
            last++;
            swap(array, last, i);
        }
    }
    
    swap (array, left, last);
    
    /* DOES NOTINHG !!!!
    qb->array = array;
    qb->left = left;
    qb->right = right;
    qb = (quicksort_arguments *) malloc(sizeof(double));
    */
    
    
    // Pack our args into a struct
    //
    *qb = quicksort_arguments_constructor(array,left,last-1);
    // Create the "left" thread
    //
    start_time = read_timer();
    if (0 == pthread_create(<, NULL, quicksort_thread_function, (void*)qb)) 
    {
        // The "right" recursion
        //
        quicksort (array, last+1, right);
        
        // Wait for the "left" recursion
        //
        pthread_join(lt, NULL);
        // Done
        //        
    //free(qb);
        return;
    }
}

So I having this currently, there are some more things but they are not "taking" part of this, where am I supposed to apply the malloc/calloc?

**EDIT** Sorry if I sound lost, because I really am. Not used to C at all.

Also forgot show how I use main.

int main (int argc, char* argv[]){
    // Our array to be sorted
    //
	int array_test[SIZE];
	/** TEST ARRAY **
    int test_array[] = {3318,3372,3212,3692,4251,3577,4271,2188,4765,3363,4912,3265,3532,4732,2135,4925,2882,1354,3939,4839,
	1814,3886,4999,1333,2328,3672,3639,4411,3396,3713,2862,4371,3445,3663,3339,3984,4378,1867,3725,3479,4892,1654,1366,3557,
	3659,3322,3593,3216,4338,4645,1366,3129,3269,4177,3125,4625,2455,3964,3766,2732,4551,4334,2989,1333,1931,1954,1794,2275,
	3832,3158,3853,3773,3318,4945,1494,1847,2114,1313,3717,3178,4465,2936,1193,1423,3396,1143,1583,2916,3913,3926,2221,3993,
	4678,2295,4444,4325,2328,3245,1921,3565,3959,3453,3983,2361,1473,3236,2949,3138,2241,4635,3844,3473,4592,1226,2648,4712,
	3523,4431,1737,1236,4337,4218,2348,4284,4835,3585,4572,2615,3483,3536,3376,3857,1386,1743,2435,3352,1633,1527,3376,3433,
	3697,2895,3298,1761,1346,4518,2776,3332,4979,2722,3162,4498,4164,2538,3833,1247,1263,3877,4699,3936,3613,3499,3533,3819,
	2542,3331,2562,3643,3356,4818,3233,3392,3824,4859,3425,3351,1173,2839,4231,4966,3135,1313,3289,2789,3619,3799,3931,4538,
	1387,2168,1153,4198,3737,3793,3633,4111,2669,3323,4317,3636};*/
    //
	int len = sizeof(array_test)/sizeof(int);
	//int len = sizeof(test_array)/sizeof(int);
	int i;
	for (i=0; i<len; i++) 
	{
		array_test[i] = i;
	}
    // We fill our array with test data. In this case just 10 to -1
    //
	printf("Unsorted\n");
    //print_array(test_array,  len);
    //print_array(array_test,len);
    
	/**/
    //quicksort(test_array, 0,  len);
	quicksort(array_test,0,len);
    end_time = read_timer();
	/**/
	printf("Sorted\n");
    //print_array(test_array,  len+1);
	//print_array(array_test,len);
	printf("The execution time is %g sec\n", end_time - start_time);
	printf("Size of array: %d",len);
    return 0;

[dargueta]

return *qa;

You're returning a copy of the struct you just allocated, so when you try to free it you're trying to free something on the stack, hence the error. Leave off the * and change the return type to a pointer.

[Turk4n]

The current setup I am using now I don't have return *qa, I have only return qa.
E.g

quicksort_arguments quicksort_arguments_constructor ( int *array, int left, int right){
	/* DOES NOTHING !!!!!
		quicksort_arguments *qa = (quicksort_arguments*) malloc(SIZE*sizeof(quicksort_arguments));
		qa->array = array;
		qa->left = left;
		qa->right = right;
		return *qa;
	*/
	quicksort_arguments qa;
    qa.array = array;
    qa.left = left;
    qa.right = right;
    return qa;
}

[dargueta]

Yes, you're allocating on the stack now. If you're going to return something from a function, never allocate it on the stack. The stack is going to get cleaned up when the function returns and your stuff will probably get overwritten or something. Go back to using malloc and make the change I specified.

[Turk4n]

So you mean ?

quicksort_arguments quicksort_arguments_constructor ( int *array, int left, int right){


		quicksort_arguments *qa = (quicksort_arguments*) malloc(SIZE*sizeof(quicksort_arguments));
		qa->array = array;
		qa->left = left;
		qa->right = right;
		return qa;


	
	/*
	quicksort_arguments qa;
    qa.array = array;
    qa.left = left;
    qa.right = right;
    return qa;*/
}

[dargueta]

Almost.

quicksort_arguments [COLOR=#ff0000][U][B]*[/B][/U][/COLOR]quicksort_arguments_constructor( ...blah blah blah... )

[Turk4n]

dargueta said:

Almost.

quicksort_arguments [COLOR=#ff0000][U][B]*[/B][/U][/COLOR]quicksort_arguments_constructor( ...blah blah blah... )

So will this mean I need to change the return to return (void*)qa ?


**EDIT**

Also I am thinking my malloc function might be wrong.

I might be sounding stupid but I am after allowing as many " things" to be sorted. Normally with structs I understand its limited. So I looked up into the fact that you can use malloc and then use as "big" you can desire.
But seems my approaches are failing me.

[dargueta]

Now that I look at it, yes it is. Get rid of SIZE.

quicksort_arguments *qa = (quicksort_arguments*) malloc(sizeof(quicksort_arguments));