I have implemented a parallel quicksort using pthreads in C. At the beginning seems to work fine but increasing the input to 10'000'000 numbers I get an unexpected segmentation-fault which I'm not able to detect and solve.
Here is my code
#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
#define SIZE 3000000
#define MAXTHREAD 10
_Atomic int count = MAXTHREAD;
_Atomic int threadid = 0;
pthread_mutex_t mutex;
void swap(int *lhs, int *rhs){
if (lhs == rhs)
return;
int tmp = *lhs;
*lhs = *rhs;
*rhs = tmp;
}
int do_pivot(int *data, int len) {
int i, pvt=0;
swap(data + (rand() % len), data+(len-1));
for (i=0; i<len; ++i)
{
if (data[i] < data[len-1])
swap(data + i, data + pvt++);
}
// swap the pivot value into position
swap(data+pvt, data+(len-1));
return pvt;
}
typedef struct {
int *data;
int len;
} array_t;
void quick_sort(int *data, int len);
void *quick_sort_thread_wrapper(void *thread_arg) {
array_t *pArray = (array_t *) thread_arg;
int *data = pArray->data;
int len = pArray->len;
quick_sort(data, len);
count ++;
free(pArray);
//printf("Count : %d\n", count);
//pthread_exit(NULL);
}
void create_quick_sort_thread(pthread_t *thread, int *data, int len) {
count--;
array_t *pArray = malloc(sizeof(array_t));
pArray->data = data;
pArray->len = len;
//printf("len %d\n", len);
pthread_create(thread, NULL, quick_sort_thread_wrapper, (void *) pArray);
//printf("ciao\n");
}
void print_array(int * data, int len){
for (int i=0; i < len; i++){
printf("%d ", data[i]);
}
printf("\n");
}
void quick_sort(int *data, int len) {
//printf("start quicksort\n");
//printf("len %d", len);
//print_array(data,len);
switch (len) {
case 2:
if (data[0] > data[1]) {
int temp = data[0];
data[0] = data[1];
data[1] = temp;
}
/* return; */
case 1:
return;
case 0:
return;
}
int pivot_pos = do_pivot(data, len);
//printf("pivot idx: %d\n", pivot_pos);
pthread_t right_thread;
int thread_started = 0;
/* pthread_mutex_lock(&mutex); */
if(count > 0){
//printf("thread_started %d\n", pivot_pos);
thread_started = 1;
create_quick_sort_thread(&right_thread, data + pivot_pos + 1, len - pivot_pos - 1);
}else{
//printf("no thread %d\n", pivot_pos);
quick_sort(data + pivot_pos + 1, len - pivot_pos -1);
}
/* pthread_mutex_unlock(&mutex); */
quick_sort(data, pivot_pos);
if (thread_started == 1){
//print_array(data,len);
//printf("waiting\n");
pthread_join(right_thread, NULL);
}
}
int main(int argc, char *argv[]) {
//int data[]= {31, 39, 59, 73, 47, 100, 57, 45, 84, 57, 35, 16, 24, 66, 92, 55, 66, 10, 65, -2, 31, 39, 59, 73, 47, 100, 57, 45, 84, 57, 35, 16, 24, 66, 92, 55, 66, 10, 65, -2};
/* int * data = malloc(sizeof(10000 * sizeof(int))); */
int p,n;
int data[SIZE];
for(int i = 0; i < SIZE; i++){
data[i]=rand() % 10000 + 1;
}
/* while(scanf(data,"%d%n", &n, &p)==1){ */
/* data[p]=n; */
/* printf("%d", data[p]); */
/* data+=p; */
/* } */
const int count = sizeof(data) / sizeof(int);
pthread_t thread;
/* printf("count %d\n", count); */
create_quick_sort_thread(&thread, data, count);
pthread_join(thread, NULL);
print_array(data,count);
//pthread_exit(NULL);
return 0;
}
What? That doesn't check
l
againstsize
, so what prevents it from stepping all over memory? Undefined behavior ...