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
|
#include "gbos.h"
/* sort [-r] [-n] [file]: sort lines, from a file or stdin.
*
* Everything is held in RAM, which bounds it: a task has 8 KiB, a file caps
* at 3 KiB, so MAXBYTES/MAXLINES are set to fit with room for the stack.
* Insertion sort - with at most 96 lines, the simple thing is fast enough and
* costs far less ROM than anything clever.
*
* ls /bin | sort | head alphabetical
* uniq -c f | sort -n -r the classic "top hits" pipeline
*
* The line store is static (it is far too big for the stack), so main() must
* copy the arguments off $A000 before touching it - see usr/ping.c. */
#define MAXBYTES 2400
#define MAXLINES 96
#define KEY MAXLINES /* scratch slot: the line being inserted */
static char store[MAXBYTES];
static unsigned int off[MAXLINES + 1];
static unsigned char len[MAXLINES + 1];
/* -> 1 if line a sorts after line b */
static unsigned char gt(unsigned char a, unsigned char b, unsigned char num) {
unsigned char i, la = len[a], lb = len[b];
if (num) { /* leading integer, if any */
unsigned int va = 0, vb = 0;
for (i = 0; i < la && store[off[a] + i] >= '0' && store[off[a] + i] <= '9'; i++)
va = va * 10 + (unsigned char)(store[off[a] + i] - '0');
for (i = 0; i < lb && store[off[b] + i] >= '0' && store[off[b] + i] <= '9'; i++)
vb = vb * 10 + (unsigned char)(store[off[b] + i] - '0');
if (va != vb) return (unsigned char)(va > vb);
}
for (i = 0; i < la && i < lb; i++) {
char ca = store[off[a] + i], cb = store[off[b] + i];
if (ca != cb) return (unsigned char)(ca > cb);
}
return (unsigned char)(la > lb);
}
void main(void) {
char args[24];
char *argv[4];
unsigned char argc, rev, num, fd = NOFD, i, j;
unsigned int used = 0;
unsigned char n = 0, clen = 0;
unsigned int cstart = 0;
char *fname = 0;
int ch;
{ /* argv lives at $A000, and so does store[] - copy the flags out first */
char *a = getargs();
for (i = 0; a[i] && i < 23; i++) args[i] = a[i];
args[i] = 0;
}
argc = 0;
{ /* tokenize our stack copy */
char *p = args;
for (;;) {
while (*p == ' ') *p++ = 0;
if (!*p) break;
if (argc < 4) argv[argc] = p;
argc++;
while (*p && *p != ' ') p++;
}
}
rev = hasflag(argv, argc, 'r');
num = hasflag(argv, argc, 'n');
for (i = 0; i < argc; i++)
if (argv[i][0] != '-') {
fname = argv[i];
break;
}
if (fname) {
fd = open(fname, O_READ);
if (fd == EISDIR) {
puts("sort: is a directory");
nl();
sexit(2);
}
if (fd == NOFD) {
puts("sort: no such file");
nl();
sexit(2);
}
}
cstart = 0;
for (;;) {
if (fd == NOFD) {
char c = readc();
ch = (c == EOF) ? -1 : c;
} else ch = fgetc(fd);
if (ch == '\r') continue;
if (ch >= 0 && ch != '\n') {
if (used < MAXBYTES) {
store[used++] = (char)ch;
clen++;
}
continue;
}
if (ch < 0 && clen == 0) break;
if (n < MAXLINES) {
off[n] = cstart;
len[n] = clen;
n++;
}
cstart = used;
clen = 0;
if (ch < 0) break;
}
if (fd != NOFD) close(fd);
for (i = 1; i < n; i++) { /* insertion sort on the index */
off[KEY] = off[i];
len[KEY] = len[i];
j = i;
/* shift while the neighbour is on the wrong side of the key. gt()
takes table slots, so the key needs a slot of its own - reusing
slot i as scratch overwrites the entries being shifted into it. */
while (j && (gt((unsigned char)(j - 1), KEY, num) ? !rev : rev)) {
off[j] = off[j - 1];
len[j] = len[j - 1];
j--;
}
off[j] = off[KEY];
len[j] = len[KEY];
}
for (i = 0; i < n; i++) {
writes(store + off[i], len[i]);
nl();
}
}
|
