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
138
139
140
141
|
#include "csapp.h"
typedef struct {
int child_fd;
int parent_fd;
} sockpair_t;
static sockpair_t MakeSocketPair(void) {
int sv[2];
Socketpair(AF_UNIX, SOCK_STREAM, 0, sv);
return (sockpair_t){.child_fd = sv[0], .parent_fd = sv[1]};
}
static bool MaybeReadNum(int fd, int *num_p) {
return Read(fd, num_p, sizeof(int)) == sizeof(int);
}
static int ReadNum(int fd) {
int num;
if (Read(fd, &num, sizeof(int)) < sizeof(int))
app_error("ReadNum error");
return num;
}
static void WriteNum(int fd, int num) {
if (Write(fd, &num, sizeof(int)) < sizeof(int))
app_error("WriteNum error");
}
static void SendElem(int parent_fd, int child_fd, int nelem) {
WriteNum(child_fd, nelem);
for (int i = 0; i < nelem; i++)
WriteNum(child_fd, ReadNum(parent_fd));
}
static void Merge(int left_fd, int right_fd, int parent_fd) {
bool has_left = true;
bool has_right = true;
int left = ReadNum(left_fd);
int right = ReadNum(right_fd);
do {
if ((has_left && has_right) ? left < right : has_left) {
WriteNum(parent_fd, left);
has_left = MaybeReadNum(left_fd, &left);
} else {
WriteNum(parent_fd, right);
has_right = MaybeReadNum(right_fd, &right);
}
} while (has_left || has_right);
}
static void Sort(int parent_fd) {
int nelem = ReadNum(parent_fd);
if (nelem < 2) {
WriteNum(parent_fd, ReadNum(parent_fd));
Close(parent_fd);
return;
}
sockpair_t left = MakeSocketPair();
int left_fd = left.parent_fd;
int lnelem = nelem/2;
if (Fork()) {
Close(left.child_fd);
SendElem(parent_fd, left_fd, lnelem);
}
else {
Close(left.parent_fd);
Sort(left.child_fd);
return;
}
sockpair_t right = MakeSocketPair();
/* TODO: Spawn right child. */
int right_fd = right.parent_fd;
int rnelem = nelem - nelem/2;
if (Fork()) {
Close(right.child_fd);
SendElem(parent_fd, right_fd, rnelem);
}
else {
Close(right.parent_fd);
Sort(right.child_fd);
return;
}
/* TODO: Send elements to children and merge returned values afterwards. */
Merge(left_fd, right_fd, parent_fd);
/* Wait for both children. */
Wait(NULL);
Wait(NULL);
}
static int GetNumber(void) {
char buf[20];
if (fgets(buf, sizeof(buf), stdin) == NULL)
app_error("GetNumber error");
return strtol(buf, NULL, 10);
}
int main(void) {
sockpair_t sort = MakeSocketPair();
if (Fork()) {
/* parent */
int nelem = GetNumber();
if (nelem < 2)
app_error("Number of sorted elements must be at least 2!\n");
Close(sort.child_fd);
/* Write unsorted numbers to mergesort */
WriteNum(sort.parent_fd, nelem);
for (int i = 0; i < nelem; i++) {
WriteNum(sort.parent_fd, GetNumber());
}
/* Read sorted numbers from mergesort */
int prev = INT_MIN;
for (int i = 0; i < nelem; i++) {
int elem = ReadNum(sort.parent_fd);
fprintf(stderr, "%d\n", elem);
assert(prev <= elem);
prev = elem;
}
Close(sort.parent_fd);
Wait(NULL);
} else {
/* child */
Close(sort.parent_fd);
Sort(sort.child_fd);
}
return 0;
}
|
