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
|
#include <stdio.h>
#include <string.h>
/* The C Programming Language: 2nd Edition
*
* Exercise 5-7: Rewrite readlines to store lines in an array supplied by
* main rather than calling alloc to maintain storage. How much faster is
* the program?
*
*/
#define MAXLINES 5000
#define MAXLEN 1000
#define MAXBUF 500000
// An additional argument is needed so we can store addresses
int readlines(char *lineptr[], int nlines, char *in_lines);
void writelines(char *lineptr[], int nlines);
int get_line(char line[], int lim);
void q_sort(char *v[], int left, int right);
void swap(char *v[], int i, int j);
char *lineptr[MAXLINES];
int main() {
char line_store[MAXBUF]; // this is our buffer for storing lines
int nlines;
if ((nlines = readlines(lineptr, MAXLINES, line_store)) >= 0) {
q_sort(lineptr, 0, nlines - 1);
writelines(lineptr, nlines);
return 0;
} else {
printf("error: input too big to sort\n");
return 1;
}
}
/* The third argument allows us to set and reference pointers to it so the
* data inside it has structure, which is maintained by the pointers in
* lineptr[]. Each time we start a new line, the current address of
* line_store is stored, the text is stored in the buffer, and the process
* repeats. While this (arguably) uses more RAM (the buffer's rather large),
* it's marginally faster due to the allocation of RAM only one time as
* opposed to x times, where x is the number of lines processed.
*/
int readlines(char *lineptr[], int maxlines, char *line_store) {
int len, nlines, total;
char line[MAXLEN];
nlines = 0;
total = 0; // number of characters processed
while ((len = get_line(line, MAXLEN)) > 0) {
if (nlines >= maxlines || total >= MAXBUF) {
return -1;
} else {
total += len;
line[len - 1] = '\0';
lineptr[nlines++] = line_store; // copy the current spot to the array of pointers
strncpy(line_store, line, len); // copy line into line_store
line_store += len; // advance to the next available spot
}
}
return nlines;
}
void writelines(char *lineptr[], int nlines) {
while (nlines-- > 0) {
printf("%s\n", *lineptr++);
}
}
void q_sort(char *v[], int left, int right) {
int i, last;
if (left >= right) {
return;
}
swap(v, left, (left + right) / 2);
last = left;
for (i = left + 1; i <= right; i++) {
if (strcmp(v[i], v[left]) < 0) {
swap(v, ++last, i);
}
}
swap(v, left, last);
q_sort(v, left, last - 1);
q_sort(v, last + 1, right);
}
void swap(char *v[], int i, int j) {
char *temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
int get_line(char s[], int lim) {
int c, i;
for (i = 0; i < lim - 1 && (c = getchar()) != EOF && c != '\n'; ++i) {
s[i] = c;
}
if (c == '\n') {
s[i] = c;
++i;
}
s[i] = '\0';
return i;
}
|
