1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
#include "threadpool.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <pthread.h>
static size_t partition(int v[], size_t len);
/* TODO: quicksort-Implementation parallelisieren */
typedef struct quicksort_param {
int *list;
size_t len;
} quicksort_param;
TASK(int, quicksort, quicksort_param)
int quicksort(quicksort_param param) {
int *list = param.list;
size_t len = param.len;
fprintf(stderr, "Thread %ld: quicksort being called with list %p and len %ld \n", pthread_self(), (void *) list, len);
if (len <= 1) return 0;
size_t mid = partition(list, len);
quicksort_fut fut1_t = quicksortFuture((quicksort_param){list, mid});
quicksort_fut fut2_t = quicksortFuture((quicksort_param){list + mid + 1, len - mid - 1});
quicksort_fut *fut1 = quicksortAsync(& fut1_t);
quicksort_fut *fut2 = quicksortAsync(& fut2_t);
quicksortAwait(fut1);
quicksortAwait(fut2);
return 0;
}
size_t partition(int v[], size_t len) {
size_t pivot = len - 1;
size_t l = 0, r = len - 2;
int t;
while (1) {
while (l < r && v[l] < v[pivot]) ++l;
while (l < r && v[r] >= v[pivot]) --r;
if (l >= r) break;
t = v[l];
v[l] = v[r];
v[r] = t;
}
if (v[l] >= v[pivot]) {
t = v[l];
v[l] = v[pivot];
v[pivot] = t;
return l;
}
return pivot;
}
static void list_randomize(int list[], size_t len) {
for (int *p = list, *e = p + len; p < e; ++p)
*p = (int)(((((double) rand()) / RAND_MAX) - 0.5)) * (int)(len);
}
static void list_print(int list[], size_t len) {
const char *sep = "";
fputs("(", stdout);
for (int *p = list, *e = p + len; p < e; ++p, sep = ", ")
printf("%s%i", sep, *p);
fputs(")\n", stdout);
}
static int list_is_sorted(int list[], size_t len) {
for (int *p = list, *e = p + len - 1; p < e; ++p) {
if (p[0] > p[1])
return 0;
}
return 1;
}
static struct timespec time_diff(struct timespec t1, struct timespec t2) {
struct timespec result = {
.tv_sec = t2.tv_sec - t1.tv_sec,
.tv_nsec = t2.tv_nsec - t1.tv_nsec
};
if (t2.tv_nsec - t1.tv_nsec < 0) {
result.tv_sec = t2.tv_sec - t1.tv_sec - 1;
result.tv_nsec = 1000000000l + t2.tv_nsec - t1.tv_nsec;
}
return result;
}
int main(int argc, const char *argv[]) {
if (tpInit(8) != 0)
perror("Thread Pool initialization failed"), exit(-1);
atexit(&tpRelease);
/* read the length of the list from the command line */
size_t list_len = 30000000;
if (argc >= 2) {
long arg = strtol(argv[1], (char **)&argv[strlen(argv[1])], 10);
if (arg > 0)
list_len = (size_t)arg;
}
/* generate a list with random integers */
int *list = malloc(sizeof(int) * list_len);
list_randomize(list, list_len);
printf("Len: %lu\n", list_len);
/* print the unsorted list if it's not too long */
printf("---- Unsortiert: %i ----\n", list_is_sorted(list, list_len));
if (list_len <= 100)
list_print(list, list_len);
/* sort it and print the sorted list if it's not too long */
struct timespec start, end, dt;
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
quicksort((quicksort_param){list, list_len});
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);
dt = time_diff(start, end);
printf("---- Sortiert: %i ----\n", list_is_sorted(list, list_len));
if (list_len <= 100)
list_print(list, list_len);
printf("Dauer: %lis %lins\n", dt.tv_sec, dt.tv_nsec);
return 0;
}
|
