aboutsummaryrefslogtreecommitdiff
path: root/sort.c
diff options
context:
space:
mode:
Diffstat (limited to 'sort.c')
-rw-r--r--sort.c385
1 files changed, 193 insertions, 192 deletions
diff --git a/sort.c b/sort.c
index d529ce722..609c5e08c 100644
--- a/sort.c
+++ b/sort.c
@@ -1,3 +1,4 @@
1/* vi: set sw=4 ts=4: */
1/* 2/*
2 * Mini sort implementation for busybox 3 * Mini sort implementation for busybox
3 * 4 *
@@ -28,29 +29,27 @@
28#include <stdio.h> 29#include <stdio.h>
29#include <errno.h> 30#include <errno.h>
30 31
31static const char sort_usage[] = 32static const char sort_usage[] = "sort [OPTION]... [FILE]...\n\n";
32"sort [OPTION]... [FILE]...\n\n"
33;
34 33
35/* typedefs _______________________________________________________________ */ 34/* typedefs _______________________________________________________________ */
36 35
37/* line node */ 36/* line node */
38typedef struct Line { 37typedef struct Line {
39 char *data; /* line data */ 38 char *data; /* line data */
40 struct Line *next; /* pointer to next line node */ 39 struct Line *next; /* pointer to next line node */
41} Line; 40} Line;
42 41
43/* singly-linked list of lines */ 42/* singly-linked list of lines */
44typedef struct { 43typedef struct {
45 int len; /* number of Lines */ 44 int len; /* number of Lines */
46 Line **sorted; /* array fed to qsort */ 45 Line **sorted; /* array fed to qsort */
47 46
48 Line *head; /* head of List */ 47 Line *head; /* head of List */
49 Line *current; /* current Line */ 48 Line *current; /* current Line */
50} List; 49} List;
51 50
52/* comparison function */ 51/* comparison function */
53typedef int (Compare)(const void *, const void *); 52typedef int (Compare) (const void *, const void *);
54 53
55 54
56/* methods ________________________________________________________________ */ 55/* methods ________________________________________________________________ */
@@ -58,175 +57,176 @@ typedef int (Compare)(const void *, const void *);
58static const int max = 1024; 57static const int max = 1024;
59 58
60/* mallocate Line */ 59/* mallocate Line */
61static Line * 60static Line *line_alloc()
62line_alloc()
63{ 61{
64 Line *self; 62 Line *self;
65 self = malloc(1 * sizeof(Line)); 63
66 return self; 64 self = malloc(1 * sizeof(Line));
65 return self;
67} 66}
68 67
69/* Initialize Line with string */ 68/* Initialize Line with string */
70static Line * 69static Line *line_init(Line * self, const char *string)
71line_init(Line *self, const char *string)
72{ 70{
73 self->data = malloc((strlen(string) + 1) * sizeof(char)); 71 self->data = malloc((strlen(string) + 1) * sizeof(char));
74 if (self->data == NULL) { return NULL; } 72
75 strcpy(self->data, string); 73 if (self->data == NULL) {
76 self->next = NULL; 74 return NULL;
77 return self; 75 }
76 strcpy(self->data, string);
77 self->next = NULL;
78 return self;
78} 79}
79 80
80/* Construct Line from FILE* */ 81/* Construct Line from FILE* */
81static Line * 82static Line *line_newFromFile(FILE * src)
82line_newFromFile(FILE *src)
83{ 83{
84 char buffer[max]; 84 char buffer[max];
85 Line *self; 85 Line *self;
86 86
87 if (fgets(buffer, max, src)) { 87 if (fgets(buffer, max, src)) {
88 self = line_alloc(); 88 self = line_alloc();
89 if (self == NULL) { return NULL; } 89 if (self == NULL) {
90 line_init(self, buffer); 90 return NULL;
91 return self; 91 }
92 } 92 line_init(self, buffer);
93 return NULL; 93 return self;
94 }
95 return NULL;
94} 96}
95 97
96/* Line destructor */ 98/* Line destructor */
97static Line * 99static Line *line_release(Line * self)
98line_release(Line *self)
99{ 100{
100 if (self->data) { 101 if (self->data) {
101 free(self->data); 102 free(self->data);
102 free(self); 103 free(self);
103 } 104 }
104 return self; 105 return self;
105} 106}
106 107
107 108
108/* Comparison */ 109/* Comparison */
109 110
110/* ascii order */ 111/* ascii order */
111static int 112static int compare_ascii(const void *a, const void *b)
112compare_ascii(const void *a, const void *b)
113{ 113{
114 Line **doh; 114 Line **doh;
115 Line *x, *y; 115 Line *x, *y;
116 116
117 doh = (Line **) a; 117 doh = (Line **) a;
118 x = *doh; 118 x = *doh;
119 doh = (Line **) b; 119 doh = (Line **) b;
120 y = *doh; 120 y = *doh;
121 121
122 // fprintf(stdout, "> %p: %s< %p: %s", x, x->data, y, y->data); 122 // fprintf(stdout, "> %p: %s< %p: %s", x, x->data, y, y->data);
123 return strcmp(x->data, y->data); 123 return strcmp(x->data, y->data);
124} 124}
125 125
126/* numeric order */ 126/* numeric order */
127static int 127static int compare_numeric(const void *a, const void *b)
128compare_numeric(const void *a, const void *b)
129{ 128{
130 Line **doh; 129 Line **doh;
131 Line *x, *y; 130 Line *x, *y;
132 int xint, yint; 131 int xint, yint;
133 132
134 doh = (Line **) a; 133 doh = (Line **) a;
135 x = *doh; 134 x = *doh;
136 doh = (Line **) b; 135 doh = (Line **) b;
137 y = *doh; 136 y = *doh;
138 137
139 xint = strtoul(x->data, NULL, 10); 138 xint = strtoul(x->data, NULL, 10);
140 yint = strtoul(y->data, NULL, 10); 139 yint = strtoul(y->data, NULL, 10);
141 140
142 return (xint - yint); 141 return (xint - yint);
143} 142}
144 143
145 144
146/* List */ 145/* List */
147 146
148/* */ 147/* */
149static List * 148static List *list_init(List * self)
150list_init(List *self)
151{ 149{
152 self->len = 0; 150 self->len = 0;
153 self->sorted = NULL; 151 self->sorted = NULL;
154 self->head = NULL; 152 self->head = NULL;
155 self->current = NULL; 153 self->current = NULL;
156 return self; 154 return self;
157} 155}
158 156
159/* for simplicity, the List gains ownership of the line */ 157/* for simplicity, the List gains ownership of the line */
160static List * 158static List *list_insert(List * self, Line * line)
161list_insert(List *self, Line *line)
162{ 159{
163 if (line == NULL) { return NULL; } 160 if (line == NULL) {
164 161 return NULL;
165 /* first insertion */ 162 }
166 if (self->head == NULL) { 163
167 self->head = line; 164 /* first insertion */
168 self->current = line; 165 if (self->head == NULL) {
169 166 self->head = line;
170 /* all subsequent insertions */ 167 self->current = line;
171 } else { 168
172 self->current->next = line; 169 /* all subsequent insertions */
173 self->current = line; 170 } else {
174 } 171 self->current->next = line;
175 self->len++; 172 self->current = line;
176 return self; 173 }
174 self->len++;
175 return self;
177} 176}
178 177
179/* order the list according to compare() */ 178/* order the list according to compare() */
180static List * 179static List *list_sort(List * self, Compare * compare)
181list_sort(List *self, Compare *compare)
182{ 180{
183 int i; 181 int i;
184 Line *line; 182 Line *line;
185 183
186 /* mallocate array of Line*s */ 184 /* mallocate array of Line*s */
187 self->sorted = (Line **) malloc(self->len * sizeof(Line*)); 185 self->sorted = (Line **) malloc(self->len * sizeof(Line *));
188 if (self->sorted == NULL) { return NULL; } 186 if (self->sorted == NULL) {
189 187 return NULL;
190 /* fill array w/ List's contents */ 188 }
191 i = 0; 189
192 line = self->head; 190 /* fill array w/ List's contents */
193 while (line) { 191 i = 0;
194 self->sorted[i++] = line; 192 line = self->head;
195 line = line->next; 193 while (line) {
196 } 194 self->sorted[i++] = line;
197 195 line = line->next;
198 /* apply qsort */ 196 }
199 qsort(self->sorted, self->len, sizeof(Line*), compare); 197
200 return self; 198 /* apply qsort */
199 qsort(self->sorted, self->len, sizeof(Line *), compare);
200 return self;
201} 201}
202 202
203/* precondition: list must be sorted */ 203/* precondition: list must be sorted */
204static List * 204static List *list_writeToFile(List * self, FILE * dst)
205list_writeToFile(List *self, FILE* dst)
206{ 205{
207 int i; 206 int i;
208 Line **line = self->sorted; 207 Line **line = self->sorted;
209 208
210 if (self->sorted == NULL) { return NULL; } 209 if (self->sorted == NULL) {
211 for (i = 0; i < self->len; i++) { 210 return NULL;
212 fprintf(dst, "%s", line[i]->data); 211 }
213 } 212 for (i = 0; i < self->len; i++) {
214 return self; 213 fprintf(dst, "%s", line[i]->data);
214 }
215 return self;
215} 216}
216 217
217/* deallocate */ 218/* deallocate */
218static void 219static void list_release(List * self)
219list_release(List *self)
220{ 220{
221 Line *i; 221 Line *i;
222 Line *die; 222 Line *die;
223 223
224 i = self->head; 224 i = self->head;
225 while (i) { 225 while (i) {
226 die = i; 226 die = i;
227 i = die->next; 227 i = die->next;
228 line_release(die); 228 line_release(die);
229 } 229 }
230} 230}
231 231
232 232
@@ -237,76 +237,77 @@ list_release(List *self)
237 * and finally print it 237 * and finally print it
238 */ 238 */
239 239
240int 240int sort_main(int argc, char **argv)
241sort_main(int argc, char **argv)
242{ 241{
243 int i; 242 int i;
244 char opt; 243 char opt;
245 List list; 244 List list;
246 Line *l; 245 Line *l;
247 Compare *compare; 246 Compare *compare;
248 247
249 /* init */ 248 /* init */
250 compare = compare_ascii; 249 compare = compare_ascii;
251 list_init(&list); 250 list_init(&list);
252 251
253 /* parse argv[] */ 252 /* parse argv[] */
254 for (i = 1; i < argc; i++) { 253 for (i = 1; i < argc; i++) {
255 if (argv[i][0] == '-') { 254 if (argv[i][0] == '-') {
256 opt = argv[i][1]; 255 opt = argv[i][1];
257 switch (opt) { 256 switch (opt) {
258 case 'g': 257 case 'g':
259 /* what's the diff between -g && -n? */ 258 /* what's the diff between -g && -n? */
260 compare = compare_numeric; 259 compare = compare_numeric;
261 break; 260 break;
262 case 'h': 261 case 'h':
263 usage(sort_usage); 262 usage(sort_usage);
264 break; 263 break;
265 case 'n': 264 case 'n':
266 /* what's the diff between -g && -n? */ 265 /* what's the diff between -g && -n? */
267 compare = compare_numeric; 266 compare = compare_numeric;
268 break; 267 break;
269 case 'r': 268 case 'r':
270 /* reverse */ 269 /* reverse */
271 break; 270 break;
272 default: 271 default:
273 fprintf(stderr, "sort: invalid option -- %c\n", opt); 272 fprintf(stderr, "sort: invalid option -- %c\n", opt);
274 usage(sort_usage); 273 usage(sort_usage);
275 } 274 }
276 } else { 275 } else {
277 break; 276 break;
277 }
278 } 278 }
279 }
280 279
281 /* this could be factored better */ 280 /* this could be factored better */
282 281
283 /* work w/ stdin */ 282 /* work w/ stdin */
284 if (i >= argc) { 283 if (i >= argc) {
285 while ( (l = line_newFromFile(stdin))) { 284 while ((l = line_newFromFile(stdin))) {
286 list_insert(&list, l); 285 list_insert(&list, l);
287 } 286 }
288 list_sort(&list, compare); 287 list_sort(&list, compare);
289 list_writeToFile(&list, stdout); 288 list_writeToFile(&list, stdout);
290 list_release(&list); 289 list_release(&list);
291 290
292 /* work w/ what's left in argv[] */ 291 /* work w/ what's left in argv[] */
293 } else { 292 } else {
294 FILE *src; 293 FILE *src;
295 294
296 for ( ; i < argc; i++) { 295 for (; i < argc; i++) {
297 src = fopen(argv[i], "r"); 296 src = fopen(argv[i], "r");
298 if (src == NULL) { break; } 297 if (src == NULL) {
299 while ( (l = line_newFromFile(src))) { 298 break;
300 list_insert(&list, l); 299 }
301 } 300 while ((l = line_newFromFile(src))) {
302 fclose(src); 301 list_insert(&list, l);
302 }
303 fclose(src);
304 }
305 list_sort(&list, compare);
306 list_writeToFile(&list, stdout);
307 list_release(&list);
303 } 308 }
304 list_sort(&list, compare);
305 list_writeToFile(&list, stdout);
306 list_release(&list);
307 }
308 309
309 exit(0); 310 exit(0);
310} 311}
311 312
312/* $Id: sort.c,v 1.10 2000/02/07 05:29:42 erik Exp $ */ 313/* $Id: sort.c,v 1.11 2000/02/08 19:58:47 erik Exp $ */
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-28 09:47:50 +0000