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
|
#include "csapp.h"
static void InsertionSort(long table[], size_t left, size_t right) {
for (size_t pivot = left + 1; pivot <= right; pivot++) {
size_t insert = left;
while ((insert < pivot) && (table[insert] < table[pivot]))
insert++;
if (insert < pivot) {
size_t n = pivot - insert;
long tmp = table[pivot];
memmove(&table[insert + 1], &table[insert], n * sizeof(long));
table[insert] = tmp;
}
}
}
static void SwapElem(long table[], size_t i, size_t j) {
long tmp = table[i];
table[i] = table[j];
table[j] = tmp;
}
static size_t Partition(long table[], size_t begin, size_t end, long pivot) {
size_t left = begin;
size_t right = end;
while (left < right) {
while ((left < right) && (table[left] < pivot))
left++;
while ((left < right) && (table[right] >= pivot))
right--;
if (left < right)
SwapElem(table, left, right);
}
return left;
}
#define INSERTSORT_MAX 32
#define FORKSORT_MIN (1L << 18)
static int QuickSort(long table[], size_t left, size_t right) {
pid_t pid_left = -1, pid_right = -1, pid = -1;
/* TODO: If there is more to sort than FORKSORT_MIN start a subprocess. */
// bool forked = false;
// if (right - left >= FORKSORT_MIN) {
// if ((pid = Fork())) {
// return pid;
// } else {
// forked = true;
// }
// }
if (left < right) {
if (right - left <= INSERTSORT_MAX) {
InsertionSort(table, left, right);
} else {
size_t pivot = left + random() % (right - left + 1);
size_t split = Partition(table, left, right, table[pivot]);
if (left == split) {
SwapElem(table, left, pivot);
split++;
} else {
pid_left = QuickSort(table, left, split - 1);
}
pid_right = QuickSort(table, split, right);
/* TODO: Wait for possible children and exit if created a subprocess. */
// if (pid_left != -1) {
// waitpid(pid_left, NULL, 0);
// }
// if (pid_right != -1) {
// waitpid(pid_right, NULL, 0);
// }
// if (forked) exit(EXIT_SUCCESS);
}
}
return pid;
}
#define NELEMS (1L << 26)
int main(void) {
/* Table size in bytes must be divisible by page size. */
size_t size = NELEMS * sizeof(long);
assert((size & (getpagesize() - 1)) == 0);
/* Initialize PRNG seed. */
struct timeval tv;
gettimeofday(&tv, NULL);
srandom(tv.tv_usec);
/* TODO: Allocate table... */
long *table = mmap(NULL, size, PROT_WRITE | PROT_READ, MAP_SHARED | MAP_ANONYMOUS, -1, 0);
/* ... and fill it in with random elements. */
for (size_t i = 0; i < NELEMS; i++)
table[i] = random();
/* Sort it using hybrid algorithm... */
if (QuickSort(table, 0, NELEMS - 1) > 0)
Wait(NULL);
/* ... and verify if the table is actually sorted. */
long prev = LONG_MIN;
for (size_t i = 0; i < NELEMS; i++) {
assert(prev <= table[i]);
prev = table[i];
}
return 0;
}
|
