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#include "libbb.h"
92
93
94enum {
95 FLAG_n = 1 << 0,
96 FLAG_g = 1 << 1,
97 FLAG_M = 1 << 2,
98 FLAG_V = 1 << 3,
99
100 FLAG_u = 1 << 4,
101 FLAG_c = 1 << 5,
102 FLAG_s = 1 << 6,
103 FLAG_z = 1 << 7,
104
105 FLAG_b = 1 << 8,
106 FLAG_r = 1 << 9,
107 FLAG_d = 1 << 10,
108 FLAG_f = 1 << 11,
109 FLAG_i = 1 << 12,
110 FLAG_m = 1 << 13,
111 FLAG_S = 1 << 14,
112 FLAG_T = 1 << 15,
113 FLAG_o = 1 << 16,
114 FLAG_k = 1 << 17,
115 FLAG_t = 1 << 18,
116 FLAG_bb = 0x80000000,
117 FLAG_no_tie_break = 0x40000000,
118};
119
120static const char sort_opt_str[] ALIGN1 = "^"
121 "ngMVucszbrdfimS:T:o:k:*t:"
122 "\0" "o--o:t--t";
123
124
125
126
127#define OPT_STR (sort_opt_str + 1)
128
129#if ENABLE_FEATURE_SORT_BIG
130static char key_separator;
131
132static struct sort_key {
133 struct sort_key *next_key;
134 unsigned range[4];
135 unsigned flags;
136} *key_list;
137
138
139
140
141
142static char *get_key(char *str, struct sort_key *key, int flags)
143{
144 int start = start;
145 int end;
146 int len, j;
147 unsigned i;
148
149
150 if (key->range[0] == 1 && !key->range[1] && !key->range[2] && !key->range[3]
151 && !(flags & (FLAG_b | FLAG_d | FLAG_f | FLAG_i | FLAG_bb))
152 ) {
153 return str;
154 }
155
156
157 len = strlen(str);
158 for (j = 0; j < 2; j++) {
159 if (!key->range[2*j])
160 end = len;
161
162 else {
163 unsigned char ch = 0;
164
165 end = 0;
166 for (i = 1; i < key->range[2*j] + j; i++) {
167 if (key_separator) {
168
169 while ((ch = str[end]) != '\0') {
170 end++;
171 if (ch == key_separator)
172 break;
173 }
174 } else {
175
176 while (isspace(str[end]))
177 end++;
178
179 while (str[end] != '\0') {
180 if (isspace(str[end]))
181 break;
182 end++;
183 }
184 }
185 }
186
187 if (j && ch) {
188
189
190
191
192 end--;
193 }
194 }
195 if (!j) start = end;
196 }
197
198 if (flags & FLAG_b)
199
200 while (isspace(str[start])) start++;
201
202 if (flags & FLAG_bb)
203 while (end > start && isspace(str[end-1])) end--;
204
205 if (key->range[3]) {
206 end = key->range[3];
207 if (end > len) end = len;
208 }
209
210 if (key->range[1]) {
211 start += key->range[1] - 1;
212 if (start > len) start = len;
213 }
214
215 if (end < start)
216 end = start;
217 str = xstrndup(str+start, end-start);
218
219 if (flags & FLAG_d) {
220 for (start = end = 0; str[end]; end++)
221 if (isspace(str[end]) || isalnum(str[end]))
222 str[start++] = str[end];
223 str[start] = '\0';
224 }
225
226 if (flags & FLAG_i) {
227 for (start = end = 0; str[end]; end++)
228 if (isprint_asciionly(str[end]))
229 str[start++] = str[end];
230 str[start] = '\0';
231 }
232
233 if (flags & FLAG_f)
234 for (i = 0; str[i]; i++)
235 str[i] = toupper(str[i]);
236
237 return str;
238}
239
240static struct sort_key *add_key(void)
241{
242 struct sort_key **pkey = &key_list;
243 while (*pkey)
244 pkey = &((*pkey)->next_key);
245 return *pkey = xzalloc(sizeof(struct sort_key));
246}
247
248#define GET_LINE(fp) \
249 ((option_mask32 & FLAG_z) \
250 ? bb_get_chunk_from_file(fp, NULL) \
251 : xmalloc_fgetline(fp))
252#else
253#define GET_LINE(fp) xmalloc_fgetline(fp)
254#endif
255
256
257static int compare_keys(const void *xarg, const void *yarg)
258{
259 int flags = option_mask32, retval = 0;
260 char *x, *y;
261
262#if ENABLE_FEATURE_SORT_BIG
263 struct sort_key *key;
264
265 for (key = key_list; !retval && key; key = key->next_key) {
266 flags = key->flags ? key->flags : option_mask32;
267
268 x = get_key(*(char **)xarg, key, flags);
269 y = get_key(*(char **)yarg, key, flags);
270#else
271
272
273 {
274 x = *(char **)xarg;
275 y = *(char **)yarg;
276#endif
277
278 switch (flags & (FLAG_n | FLAG_g | FLAG_M | FLAG_V)) {
279 default:
280 bb_error_msg_and_die("unknown sort type");
281 break;
282#if defined(HAVE_STRVERSCMP) && HAVE_STRVERSCMP == 1
283 case FLAG_V:
284 retval = strverscmp(x, y);
285 break;
286#endif
287
288 case 0:
289#if ENABLE_LOCALE_SUPPORT
290 retval = strcoll(x, y);
291#else
292 retval = strcmp(x, y);
293#endif
294 break;
295#if ENABLE_FEATURE_SORT_BIG
296 case FLAG_g: {
297 char *xx, *yy;
298 double dx = strtod(x, &xx);
299 double dy = strtod(y, &yy);
300
301 if (x == xx)
302 retval = (y == yy ? 0 : -1);
303 else if (y == yy)
304 retval = 1;
305
306 else if (dx != dx)
307 retval = (dy != dy) ? 0 : -1;
308 else if (dy != dy)
309 retval = 1;
310
311 else if (1.0 / dx == 0.0) {
312 if (dx < 0)
313 retval = (1.0 / dy == 0.0 && dy < 0) ? 0 : -1;
314 else
315 retval = (1.0 / dy == 0.0 && dy > 0) ? 0 : 1;
316 } else if (1.0 / dy == 0.0)
317 retval = (dy < 0) ? 1 : -1;
318 else
319 retval = (dx > dy) ? 1 : ((dx < dy) ? -1 : 0);
320 break;
321 }
322 case FLAG_M: {
323 struct tm thyme;
324 int dx;
325 char *xx, *yy;
326
327 xx = strptime(x, "%b", &thyme);
328 dx = thyme.tm_mon;
329 yy = strptime(y, "%b", &thyme);
330 if (!xx)
331 retval = (!yy) ? 0 : -1;
332 else if (!yy)
333 retval = 1;
334 else
335 retval = dx - thyme.tm_mon;
336 break;
337 }
338
339 case FLAG_n: {
340 double dx = atof(x);
341 double dy = atof(y);
342 retval = (dx > dy) ? 1 : ((dx < dy) ? -1 : 0);
343 break;
344 }
345 }
346
347 if (x != *(char **)xarg) free(x);
348 if (y != *(char **)yarg) free(y);
349
350#else
351
352 case FLAG_n:
353 retval = atoi(x) - atoi(y);
354 break;
355 }
356#endif
357 }
358
359 if (retval == 0) {
360
361
362 if (option_mask32 & FLAG_s) {
363
364
365
366 uint32_t *p32;
367 uint32_t x32, y32;
368 char *line;
369 unsigned len;
370
371 line = *(char**)xarg;
372 len = (strlen(line) + 4) & (~3u);
373 p32 = (void*)(line + len);
374 x32 = *p32;
375 line = *(char**)yarg;
376 len = (strlen(line) + 4) & (~3u);
377 p32 = (void*)(line + len);
378 y32 = *p32;
379
380
381 retval = (x32 > y32) * 2 - 1;
382 } else
383 if (!(option_mask32 & FLAG_no_tie_break)) {
384
385 flags = option_mask32;
386 retval = strcmp(*(char **)xarg, *(char **)yarg);
387 }
388 }
389
390 if (flags & FLAG_r)
391 return -retval;
392
393 return retval;
394}
395
396#if ENABLE_FEATURE_SORT_BIG
397static unsigned str2u(char **str)
398{
399 unsigned long lu;
400 if (!isdigit((*str)[0]))
401 bb_error_msg_and_die("bad field specification");
402 lu = strtoul(*str, str, 10);
403 if ((sizeof(long) > sizeof(int) && lu > INT_MAX) || !lu)
404 bb_error_msg_and_die("bad field specification");
405 return lu;
406}
407#endif
408
409int sort_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
410int sort_main(int argc UNUSED_PARAM, char **argv)
411{
412 char **lines;
413 char *str_ignored, *str_o, *str_t;
414 llist_t *lst_k = NULL;
415 int i;
416 int linecount;
417 unsigned opts;
418#if ENABLE_FEATURE_SORT_OPTIMIZE_MEMORY
419 bool can_drop_dups;
420 size_t prev_len = 0;
421 char *prev_line = (char*) "";
422
423
424
425 size_t count_to_optimize_dups = 0x3fff;
426#endif
427
428 xfunc_error_retval = 2;
429
430
431 opts = getopt32(argv,
432 sort_opt_str,
433 &str_ignored, &str_ignored, &str_o, &lst_k, &str_t
434 );
435#if ENABLE_FEATURE_SORT_OPTIMIZE_MEMORY
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451 can_drop_dups = ((opts & ~(FLAG_o|FLAG_z|FLAG_r|FLAG_s)) == FLAG_u);
452
453
454
455 if (opts & FLAG_s)
456 count_to_optimize_dups = (size_t)-1L;
457#endif
458
459 if (opts & FLAG_b)
460 option_mask32 |= FLAG_bb;
461#if ENABLE_FEATURE_SORT_BIG
462 if (opts & FLAG_t) {
463 if (!str_t[0] || str_t[1])
464 bb_error_msg_and_die("bad -t parameter");
465 key_separator = str_t[0];
466 }
467
468
469
470
471 while (lst_k) {
472 enum {
473 FLAG_allowed_for_k =
474 FLAG_n |
475 FLAG_g |
476 FLAG_M |
477 FLAG_b |
478 FLAG_r |
479 FLAG_d |
480 FLAG_f |
481 FLAG_i |
482 0
483 };
484 struct sort_key *key = add_key();
485 char *str_k = llist_pop(&lst_k);
486
487 i = 0;
488 while (*str_k) {
489
490
491 key->range[2*i] = str2u(&str_k);
492 if (*str_k == '.') {
493 str_k++;
494 key->range[2*i+1] = str2u(&str_k);
495 }
496 while (*str_k) {
497 int flag;
498 const char *idx;
499
500 if (*str_k == ',' && !i++) {
501 str_k++;
502 break;
503 }
504
505 idx = strchr(OPT_STR, *str_k);
506 if (!idx)
507 bb_error_msg_and_die("unknown key option");
508 flag = 1 << (idx - OPT_STR);
509 if (flag & ~FLAG_allowed_for_k)
510 bb_error_msg_and_die("unknown sort type");
511
512 if (i && flag == FLAG_b)
513 flag = FLAG_bb;
514 key->flags |= flag;
515 str_k++;
516 }
517 }
518 }
519#endif
520
521
522 argv += optind;
523 if (!*argv)
524 *--argv = (char*)"-";
525 linecount = 0;
526 lines = NULL;
527 do {
528
529
530 FILE *fp = xfopen_stdin(*argv);
531 for (;;) {
532 char *line = GET_LINE(fp);
533 if (!line)
534 break;
535
536#if ENABLE_FEATURE_SORT_OPTIMIZE_MEMORY
537 if (count_to_optimize_dups != 0)
538 count_to_optimize_dups--;
539 if (count_to_optimize_dups == 0) {
540 size_t len;
541 char *new_line;
542
543
544
545
546
547
548 len = strlen(line);
549 if (len <= prev_len) {
550 new_line = prev_line + (prev_len - len);
551 if (strcmp(line, new_line) == 0) {
552
553 if (can_drop_dups && prev_len == len) {
554
555 free(line);
556 continue;
557 }
558 free(line);
559 line = new_line;
560
561
562
563 goto skip;
564 }
565 }
566 prev_len = len;
567 prev_line = line;
568 skip: ;
569 }
570#else
571
572#endif
573 lines = xrealloc_vector(lines, 6, linecount);
574 lines[linecount++] = line;
575 }
576 fclose_if_not_stdin(fp);
577 } while (*++argv);
578
579#if ENABLE_FEATURE_SORT_BIG
580
581 if (!key_list)
582 add_key()->range[0] = 1;
583
584 if (option_mask32 & FLAG_c) {
585 int j = (option_mask32 & FLAG_u) ? -1 : 0;
586 for (i = 1; i < linecount; i++) {
587 if (compare_keys(&lines[i-1], &lines[i]) > j) {
588 fprintf(stderr, "Check line %u\n", i);
589 return EXIT_FAILURE;
590 }
591 }
592 return EXIT_SUCCESS;
593 }
594#endif
595
596
597 if (option_mask32 & FLAG_s) {
598 for (i = 0; i < linecount; i++) {
599 uint32_t *p32;
600 char *line;
601 unsigned len;
602
603 line = lines[i];
604 len = (strlen(line) + 4) & (~3u);
605 lines[i] = line = xrealloc(line, len + 4);
606 p32 = (void*)(line + len);
607 *p32 = i;
608 }
609
610
611 }
612
613
614 qsort(lines, linecount, sizeof(lines[0]), compare_keys);
615
616
617 if (option_mask32 & FLAG_u) {
618 int j = 0;
619
620
621
622
623 option_mask32 |= FLAG_no_tie_break;
624 for (i = 1; i < linecount; i++) {
625 if (compare_keys(&lines[j], &lines[i]) == 0)
626 free(lines[i]);
627 else
628 lines[++j] = lines[i];
629 }
630 if (linecount)
631 linecount = j+1;
632 }
633
634
635#if ENABLE_FEATURE_SORT_BIG
636
637 if (option_mask32 & FLAG_o)
638 xmove_fd(xopen(str_o, O_WRONLY|O_CREAT|O_TRUNC), STDOUT_FILENO);
639#endif
640 {
641 int ch = (option_mask32 & FLAG_z) ? '\0' : '\n';
642 for (i = 0; i < linecount; i++)
643 printf("%s%c", lines[i], ch);
644 }
645
646 fflush_stdout_and_exit(EXIT_SUCCESS);
647}
648