I'm threading a template-based mergesort using pthreads/nptl. Problem
is, I have a function that takes void* as input and I don't want to
use typeid/RTTI because I'm threading it to make it faster on
multicore cpus and I want everything to be done at compile time.
code:
#include
#include
#include
#include
/* mergesort, using pointers */
template
void mergesort_p(T* start, T* end) {
T *mid, *shift, t;
pthread_t threads[2];
TwoPointers *startend;
if (start >= end) return; //recursed deep enough (1 element)
//recursively sort halves of the list
mid = (T*)(start + ((end - start) >> 1));
startend = new TwoPointers(start, mid);
pthread_create(&threads[0], NULL, mergesort_thread,
reinterpret_cast(startend));
startend->p1 = mid + 1;
startend->p2 = end;
pthread_create(&threads[1], NULL, mergesort_thread,
reinterpret_cast(startend));
for (;(start <= mid) && (mid + 1 <= end); start++) {
if (*start < *(mid + 1)) //sorted (current element belongs in 1st
half)
continue;
else { /* true inplace merge requires insersion-sort-like
* methods because a value from the second half is inserted to
* the current element */
//copy the first element in the second half to t
t = *(mid + 1);
//shift first half to the right
for (shift = mid; shift >= start; shift--)
*(shift + 1) = *shift;
//copy t to start
*start = t;
mid++;
}
}
};
template
void mergesort_thread(void *pointers)
pthread_t threads[2];
TwoPointers *startend = reinterpret_cast(pointers);
//How do I define the type of T here without using typeid?
T *mid, *shift, t;
T* start = (TwoPointers)pointers->p1;
T* end = (TwoPointers)pointers->p2;
if (start >= end) return; //recursed deep enough (1 element)
//recursively sort halves of the list
mid = (T*)(start + ((end - start) >> 1));
startend = new TwoPointers(start, mid);
pthread_create(&threads[0], NULL, mergesort_thread,
reinterpret_cast(startend));
startend->p1 = mid + 1;
startend->p2 = end;
pthread_create(&threads[1], NULL, mergesort_thread,
reinterpret_cast(startend));
delete startend;
pthread_join(threads[1]);
for (;(start <= mid) && (mid + 1 <= end); start++) {
if (*start < *(mid + 1)) //sorted (current element belongs in 1st
half)
continue;
else { /* true inplace merge requires insersion-sort-like
* methods because a value from the second half is inserted to
* the current element */
//copy the first element in the second half to t
t = *(mid + 1);
//shift first half to the right
for (shift = mid; shift >= start; shift--)
*(shift + 1) = *shift;
//copy t to start
*start = t;
mid++;
}
}
};
template
struct TwoPointers {
T* p1;
T* p2;
TwoPointers(T* _p1, T* _p2) : p1 = _p1, p2 = _p2 {}
};
/* mergesort wrapper */
template
void mergesort(T* array, size_t n) {
mergesort_p(array, &array[n - 1]);
};
int main(int argc, char *argv[]) {
unsigned a, b, num = 0;
unsigned *_a;
clock_t *times = (clock_t *)malloc(2 * sizeof(clock_t));
clock_t total_time;
pid_t childpid;
if (argc == 1) {
printf("Enter # of elements to sort:");
scanf("%u", &num);
} else
sscanf(argv[1], "%u", &num);
puts("allocating memory...");
_a = (unsigned *)malloc(num * sizeof(a));
total_time = clock();
puts("\ngenerating random numbers...");
times[0] = clock();
for (a = 0; a < num; a++) {
_a[a] = 0;
srand(rand());
for (b = 0; b < sizeof(unsigned) >> 1; b++)
_a[a] |= (unsigned)rand() << (b * 16);
}
times[1] = clock();
printf("%25f seconds\n", (times[1] - times[0]) /
(double)CLOCKS_PER_SEC);
puts("sorting the array...");
times[0] = clock();
mergesort(_a, num);
times[1] = clock();
printf("%25f seconds\n", (times[1] - times[0]) /
(double)CLOCKS_PER_SEC);
printf("\ntotal time: %25f seconds\n", (times[1] - total_time) /
(double)CLOCKS_PER_SEC);
return 0;
}