2 * Copyright (C) 2009 Gabor Kovesdan <gabor@FreeBSD.org>
3 * Copyright (C) 2012 Oleg Moskalenko <oleg.moskalenko@citrix.com>
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28 #include <sys/cdefs.h>
29 __FBSDID("$FreeBSD$");
33 #include <sys/types.h>
34 #include <sys/queue.h>
38 #if defined(SORT_THREADS)
41 #include <semaphore.h>
51 #include "radixsort.h"
53 unsigned long long free_memory = 1000000;
54 unsigned long long available_free_memory = 1000000;
58 const char *tmpdir = "/var/tmp";
59 const char *compress_program;
61 size_t max_open_files = 16;
64 * How much space we read from file at once
66 #define READ_CHUNK (4096)
69 * File reader structure
73 struct reader_buffer rb;
76 unsigned char *buffer;
77 unsigned char *mmapaddr;
78 unsigned char *mmapptr;
88 * Structure to be used in file merge process.
92 struct file_reader *fr;
93 struct sort_list_item *si; /* current top line */
98 * List elements of "cleanable" files list.
100 struct CLEANABLE_FILE
103 LIST_ENTRY(CLEANABLE_FILE) files;
107 * List header of "cleanable" files list.
109 static LIST_HEAD(CLEANABLE_FILES,CLEANABLE_FILE) tmp_files;
112 * Semaphore to protect the tmp file list.
113 * We use semaphore here because it is signal-safe, according to POSIX.
114 * And semaphore does not require pthread library.
116 static sem_t tmp_files_sem;
118 static void mt_sort(struct sort_list *list,
119 int (*sort_func)(void *, size_t, size_t,
120 int (*)(const void *, const void *)), const char* fn);
123 * Init tmp files list
129 LIST_INIT(&tmp_files);
130 sem_init(&tmp_files_sem, 0, 1);
134 * Save name of a tmp file for signal cleanup
137 tmp_file_atexit(const char *tmp_file)
141 sem_wait(&tmp_files_sem);
142 struct CLEANABLE_FILE *item =
143 sort_malloc(sizeof(struct CLEANABLE_FILE));
144 item->fn = sort_strdup(tmp_file);
145 LIST_INSERT_HEAD(&tmp_files, item, files);
146 sem_post(&tmp_files_sem);
154 clear_tmp_files(void)
156 struct CLEANABLE_FILE *item;
158 sem_wait(&tmp_files_sem);
159 LIST_FOREACH(item,&tmp_files,files) {
160 if ((item) && (item->fn))
163 sem_post(&tmp_files_sem);
167 * Check whether a file is a temporary file
170 file_is_tmp(const char* fn)
172 struct CLEANABLE_FILE *item;
176 sem_wait(&tmp_files_sem);
177 LIST_FOREACH(item,&tmp_files,files) {
178 if ((item) && (item->fn))
179 if (strcmp(item->fn, fn) == 0) {
184 sem_post(&tmp_files_sem);
191 * Read zero-terminated line from a file
194 read_file0_line(struct file0_reader *f0r)
199 if ((f0r->f == NULL) || feof(f0r->f))
202 if (f0r->current_line && f0r->current_sz > 0)
203 f0r->current_line[0] = 0;
205 while (!feof(f0r->f)) {
207 if (feof(f0r->f) || (c == -1))
209 if ((pos + 1) >= f0r->current_sz) {
210 size_t newsz = (f0r->current_sz + 2) * 2;
211 f0r->current_line = sort_realloc(f0r->current_line,
213 f0r->current_sz = newsz;
215 f0r->current_line[pos] = (char)c;
219 f0r->current_line[pos + 1] = 0;
223 return f0r->current_line;
227 * Generate new temporary file name
230 new_tmp_file_name(void)
232 static unsigned int tfcounter = 0;
233 static const char *fn = ".bsdsort.";
237 sz = strlen(tmpdir) + 1 + strlen(fn) + 32 + 1;
238 ret = sort_malloc(sz);
240 sprintf(ret, "%s/%s%d.%u", tmpdir, fn, (int) getpid(), tfcounter++);
241 tmp_file_atexit(ret);
246 * Initialize file list
249 file_list_init(struct file_list *fl, bool tmp)
261 * Add a file name to the list
264 file_list_add(struct file_list *fl, char *fn, bool allocate)
268 if (fl->count >= fl->sz || (fl->fns == NULL)) {
269 fl->sz = (fl->sz) * 2 + 1;
270 fl->fns = sort_realloc(fl->fns, fl->sz *
273 fl->fns[fl->count] = allocate ? sort_strdup(fn) : fn;
279 * Populate file list from array of file names
282 file_list_populate(struct file_list *fl, int argc, char **argv, bool allocate)
288 for (i = 0; i < argc; i++)
289 file_list_add(fl, argv[i], allocate);
294 * Clean file list data and delete the files,
295 * if this is a list of temporary files
298 file_list_clean(struct file_list *fl)
305 for (i = 0; i < fl->count; i++) {
309 sort_free(fl->fns[i]);
326 sort_list_init(struct sort_list *l)
332 l->memsize = sizeof(struct sort_list);
338 * Add string to sort list
341 sort_list_add(struct sort_list *l, struct bwstring *str)
345 size_t indx = l->count;
347 if ((l->list == NULL) || (indx >= l->size)) {
348 int newsize = (l->size + 1) + 1024;
350 l->list = sort_realloc(l->list,
351 sizeof(struct sort_list_item*) * newsize);
352 l->memsize += (newsize - l->size) *
353 sizeof(struct sort_list_item*);
356 l->list[indx] = sort_list_item_alloc();
357 sort_list_item_set(l->list[indx], str);
358 l->memsize += sort_list_item_size(l->list[indx]);
364 * Clean sort list data
367 sort_list_clean(struct sort_list *l)
374 for (i = 0; i < l->count; i++) {
375 struct sort_list_item *item;
380 sort_list_item_clean(item);
390 l->memsize = sizeof(struct sort_list);
395 * Write sort list to file
398 sort_list_dump(struct sort_list *l, const char *fn)
404 f = openfile(fn, "w");
410 if (!(sort_opts_vals.uflag)) {
411 for (i = 0; i < l->count; ++i)
412 bwsfwrite(l->list[i]->str, f,
413 sort_opts_vals.zflag);
415 struct sort_list_item *last_printed_item = NULL;
416 struct sort_list_item *item;
417 for (i = 0; i < l->count; ++i) {
419 if ((last_printed_item == NULL) ||
420 list_coll(&last_printed_item, &item)) {
421 bwsfwrite(item->str, f, sort_opts_vals.zflag);
422 last_printed_item = item;
433 * Checks if the given file is sorted. Stops at the first disorder,
434 * prints the disordered line and returns 1.
437 check(const char *fn)
439 struct bwstring *s1, *s2, *s1disorder, *s2disorder;
440 struct file_reader *fr;
441 struct keys_array *ka1, *ka2;
442 int res, pos, posdisorder;
444 s1 = s2 = s1disorder = s2disorder = NULL;
447 fr = file_reader_init(fn);
458 s1 = file_reader_readline(fr);
462 ka1 = keys_array_alloc();
465 s2 = file_reader_readline(fr);
469 ka2 = keys_array_alloc();
475 bwsprintf(stdout, s2, "s1=<", ">");
476 bwsprintf(stdout, s1, "s2=<", ">");
478 int cmp = key_coll(ka2, ka1, 0);
480 printf("; cmp1=%d", cmp);
482 if (!cmp && sort_opts_vals.complex_sort &&
483 !(sort_opts_vals.uflag) && !(sort_opts_vals.sflag)) {
484 cmp = top_level_str_coll(s2, s1);
486 printf("; cmp2=%d", cmp);
491 if ((sort_opts_vals.uflag && (cmp <= 0)) || (cmp < 0)) {
492 if (!(sort_opts_vals.csilentflag)) {
493 s2disorder = bwsdup(s2);
496 s1disorder = bwsdup(s1);
504 clean_keys_array(s1, ka1);
512 s2 = file_reader_readline(fr);
516 ka2 = keys_array_alloc();
522 clean_keys_array(s1, ka1);
530 clean_keys_array(s2, ka2);
537 if ((fn == NULL) || (*fn == 0) || (strcmp(fn, "-") == 0)) {
539 s2 = file_reader_readline(fr);
546 file_reader_free(fr);
549 bws_disorder_warnx(s2disorder, fn, posdisorder);
551 bws_disorder_warnx(s1disorder, fn, posdisorder);
552 if (s1disorder != s2disorder)
567 * Opens a file. If the given filename is "-", stdout will be
571 openfile(const char *fn, const char *mode)
575 if (strcmp(fn, "-") == 0) {
576 return ((mode && mode[0] == 'r') ? stdin : stdout);
578 mode_t orig_file_mask = 0;
579 int is_tmp = file_is_tmp(fn);
581 if (is_tmp && (mode[0] == 'w'))
582 orig_file_mask = umask(S_IWGRP | S_IWOTH |
585 if (is_tmp && (compress_program != NULL)) {
589 cmdsz = strlen(fn) + 128;
590 cmd = sort_malloc(cmdsz);
595 snprintf(cmd, cmdsz - 1, "cat %s | %s -d",
596 fn, compress_program);
597 else if (mode[0] == 'w')
598 snprintf(cmd, cmdsz - 1, "%s > %s",
599 compress_program, fn);
601 err(2, "%s", getstr(7));
603 if ((file = popen(cmd, mode)) == NULL)
609 if ((file = fopen(fn, mode)) == NULL)
612 if (is_tmp && (mode[0] == 'w'))
613 umask(orig_file_mask);
623 closefile(FILE *f, const char *fn)
627 } else if (f == stdin) {
629 } else if (f == stdout) {
632 if (file_is_tmp(fn) && compress_program != NULL) {
641 * Reads a file into the internal buffer.
644 file_reader_init(const char *fsrc)
646 struct file_reader *ret;
651 ret = sort_malloc(sizeof(struct file_reader));
652 memset(ret, 0, sizeof(struct file_reader));
655 if (sort_opts_vals.zflag)
658 ret->fname = sort_strdup(fsrc);
660 if (strcmp(fsrc, "-") && (compress_program == NULL) && use_mmap) {
663 struct stat stat_buf;
668 flags = MAP_NOCORE | MAP_NOSYNC;
671 fd = open(fsrc, O_RDONLY);
675 if (fstat(fd, &stat_buf) < 0) {
680 sz = stat_buf.st_size;
682 #if defined(MAP_PREFAULT_READ)
683 flags |= MAP_PREFAULT_READ;
686 addr = mmap(NULL, sz, PROT_READ, flags, fd, 0);
687 if (addr == MAP_FAILED) {
693 ret->mmapaddr = addr;
695 ret->mmapptr = ret->mmapaddr;
700 if (ret->mmapaddr == NULL) {
701 ret->file = openfile(fsrc, "r");
702 if (ret->file == NULL)
705 if (strcmp(fsrc, "-")) {
706 ret->cbsz = READ_CHUNK;
707 ret->buffer = sort_malloc(ret->cbsz);
711 ret->bsz = fread(ret->buffer, 1, ret->cbsz, ret->file);
713 if (ferror(ret->file))
723 file_reader_readline(struct file_reader *fr)
725 struct bwstring *ret = NULL;
728 unsigned char *mmapend;
730 mmapend = fr->mmapaddr + fr->mmapsize;
731 if (fr->mmapptr >= mmapend)
734 unsigned char *strend;
737 sz = mmapend - fr->mmapptr;
738 strend = memchr(fr->mmapptr, fr->elsymb, sz);
740 if (strend == NULL) {
741 ret = bwscsbdup(fr->mmapptr, sz);
742 fr->mmapptr = mmapend;
744 ret = bwscsbdup(fr->mmapptr, strend -
746 fr->mmapptr = strend + 1;
750 } else if (fr->file != stdin) {
751 unsigned char *strend;
752 size_t bsz1, remsz, search_start;
758 if (fr->bsz > fr->strbeg)
759 remsz = fr->bsz - fr->strbeg;
761 /* line read cycle */
763 if (remsz > search_start)
764 strend = memchr(fr->buffer + fr->strbeg +
765 search_start, fr->elsymb, remsz -
775 if (fr->bsz != fr->cbsz)
777 err(2, "File read software error 1");
779 if (remsz > (READ_CHUNK >> 1)) {
780 search_start = fr->cbsz - fr->strbeg;
781 fr->cbsz += READ_CHUNK;
782 fr->buffer = sort_realloc(fr->buffer,
784 bsz1 = fread(fr->buffer + fr->bsz, 1,
785 READ_CHUNK, fr->file);
787 if (ferror(fr->file))
794 if (remsz > 0 && fr->strbeg>0)
795 bcopy(fr->buffer + fr->strbeg,
799 search_start = remsz;
800 bsz1 = fread(fr->buffer + remsz, 1,
801 fr->cbsz - remsz, fr->file);
803 if (ferror(fr->file))
807 fr->bsz = remsz + bsz1;
813 strend = fr->buffer + fr->bsz;
815 if ((fr->buffer + fr->strbeg <= strend) &&
816 (fr->strbeg < fr->bsz) && (remsz>0))
817 ret = bwscsbdup(fr->buffer + fr->strbeg, strend -
818 fr->buffer - fr->strbeg);
820 fr->strbeg = (strend - fr->buffer) + 1;
825 ret = bwsfgetln(fr->file, &len, sort_opts_vals.zflag,
833 file_reader_clean(struct file_reader *fr)
838 munmap(fr->mmapaddr, fr->mmapsize);
844 sort_free(fr->buffer);
847 if (fr->file != stdin)
848 closefile(fr->file, fr->fname);
851 sort_free(fr->fname);
853 memset(fr, 0, sizeof(struct file_reader));
858 file_reader_free(struct file_reader *fr)
862 file_reader_clean(fr);
868 procfile(const char *fsrc, struct sort_list *list, struct file_list *fl)
870 struct file_reader *fr;
872 fr = file_reader_init(fsrc);
876 /* file browse cycle */
878 struct bwstring *bws;
880 bws = file_reader_readline(fr);
885 sort_list_add(list, bws);
887 if (list->memsize >= available_free_memory) {
890 fn = new_tmp_file_name();
891 sort_list_to_file(list, fn);
892 file_list_add(fl, fn, false);
893 sort_list_clean(list);
897 file_reader_free(fr);
903 * Compare file headers. Files with EOF always go to the end of the list.
906 file_header_cmp(struct file_header *f1, struct file_header *f2)
912 if (f1->fr == NULL) {
913 return ((f2->fr == NULL) ? 0 : +1);
914 } else if (f2->fr == NULL)
919 ret = list_coll(&(f1->si), &(f2->si));
921 return ((f1->file_pos < f2->file_pos) ? -1 : +1);
928 * Allocate and init file header structure
931 file_header_init(struct file_header **fh, const char *fn, size_t file_pos)
935 struct bwstring *line;
937 *fh = sort_malloc(sizeof(struct file_header));
938 (*fh)->file_pos = file_pos;
939 (*fh)->fr = file_reader_init(fn);
940 if ((*fh)->fr == NULL) {
942 err(2, "%s", getstr(8));
944 line = file_reader_readline((*fh)->fr);
946 file_reader_free((*fh)->fr);
950 (*fh)->si = sort_list_item_alloc();
951 sort_list_item_set((*fh)->si, line);
960 file_header_close(struct file_header **fh)
965 file_reader_free((*fh)->fr);
969 sort_list_item_clean((*fh)->si);
970 sort_free((*fh)->si);
979 * Swap two array elements
982 file_header_swap(struct file_header **fh, int i1, int i2)
984 struct file_header *tmp;
991 /* heap algorithm ==>> */
994 * See heap sort algorithm
995 * "Raises" last element to its right place
998 file_header_heap_swim(struct file_header **fh, int indx)
1004 parent_index = (indx - 1) >> 1;
1006 if (file_header_cmp(fh[indx], fh[parent_index]) < 0) {
1007 /* swap child and parent and continue */
1008 file_header_swap(fh, indx, parent_index);
1009 file_header_heap_swim(fh, parent_index);
1015 * Sink the top element to its correct position
1018 file_header_heap_sink(struct file_header **fh, int indx, int size)
1020 int left_child_index;
1021 int right_child_index;
1023 left_child_index = indx + indx + 1;
1024 right_child_index = left_child_index + 1;
1026 if (left_child_index < size) {
1027 int min_child_index;
1029 min_child_index = left_child_index;
1031 if ((right_child_index < size) &&
1032 (file_header_cmp(fh[left_child_index],
1033 fh[right_child_index]) > 0))
1034 min_child_index = right_child_index;
1035 if (file_header_cmp(fh[indx], fh[min_child_index]) > 0) {
1036 file_header_swap(fh, indx, min_child_index);
1037 file_header_heap_sink(fh, min_child_index, size);
1042 /* <<== heap algorithm */
1045 * Adds element to the "left" end
1048 file_header_list_rearrange_from_header(struct file_header **fh, int size)
1051 file_header_heap_sink(fh, 0, size);
1055 * Adds element to the "right" end
1058 file_header_list_push(struct file_header *f, struct file_header **fh, int size)
1062 file_header_heap_swim(fh, size - 1);
1067 struct bwstring *str;
1071 * Prints the current line of the file
1074 file_header_print(struct file_header *fh, FILE *f_out, struct last_printed *lp)
1077 if (fh && fh->fr && f_out && fh->si && fh->si->str) {
1078 if (sort_opts_vals.uflag) {
1079 if ((lp->str == NULL) || (str_list_coll(lp->str, &(fh->si)))) {
1080 bwsfwrite(fh->si->str, f_out, sort_opts_vals.zflag);
1083 lp->str = bwsdup(fh->si->str);
1086 bwsfwrite(fh->si->str, f_out, sort_opts_vals.zflag);
1094 file_header_read_next(struct file_header *fh)
1098 struct bwstring *tmp;
1100 tmp = file_reader_readline(fh->fr);
1102 file_reader_free(fh->fr);
1105 sort_list_item_clean(fh->si);
1111 fh->si = sort_list_item_alloc();
1112 sort_list_item_set(fh->si, tmp);
1118 * Merge array of "files headers"
1121 file_headers_merge(int fnum, struct file_header **fh, FILE *f_out)
1123 struct last_printed lp;
1126 memset(&lp, 0, sizeof(lp));
1129 * construct the initial sort structure
1131 for (i = 0; i < fnum; i++)
1132 file_header_list_push(fh[i], fh, i);
1134 while (fh[0]->fr) { /* unfinished files are always in front */
1135 /* output the smallest line: */
1136 file_header_print(fh[0], f_out, &lp);
1137 /* read a new line, if possible: */
1138 file_header_read_next(fh[0]);
1139 /* re-arrange the list: */
1140 file_header_list_rearrange_from_header(fh, fnum);
1148 * Merges the given files into the output file, which can be
1152 merge_files_array(int argc, char **argv, const char *fn_out)
1155 if (argv && fn_out) {
1156 struct file_header **fh;
1160 f_out = openfile(fn_out, "w");
1165 fh = sort_malloc((argc + 1) * sizeof(struct file_header *));
1167 for (i = 0; i < argc; i++)
1168 file_header_init(fh + i, argv[i], (size_t) i);
1170 file_headers_merge(argc, fh, f_out);
1172 for (i = 0; i < argc; i++)
1173 file_header_close(fh + i);
1177 closefile(f_out, fn_out);
1182 * Shrinks the file list until its size smaller than max number of opened files
1185 shrink_file_list(struct file_list *fl)
1188 if ((fl == NULL) || (size_t) (fl->count) < max_open_files)
1191 struct file_list new_fl;
1194 file_list_init(&new_fl, true);
1195 while (indx < fl->count) {
1199 num = fl->count - indx;
1200 fnew = new_tmp_file_name();
1202 if ((size_t) num >= max_open_files)
1203 num = max_open_files - 1;
1204 merge_files_array(num, fl->fns + indx, fnew);
1208 for (i = 0; i < num; i++)
1209 unlink(fl->fns[indx + i]);
1211 file_list_add(&new_fl, fnew, false);
1214 fl->tmp = false; /* already taken care of */
1215 file_list_clean(fl);
1217 fl->count = new_fl.count;
1218 fl->fns = new_fl.fns;
1220 fl->tmp = new_fl.tmp;
1227 * Merge list of files
1230 merge_files(struct file_list *fl, const char *fn_out)
1234 while (shrink_file_list(fl));
1236 merge_files_array(fl->count, fl->fns, fn_out);
1241 get_sort_method_name(int sm)
1244 if (sm == SORT_MERGESORT)
1246 else if (sort_opts_vals.sort_method == SORT_RADIXSORT)
1248 else if (sort_opts_vals.sort_method == SORT_HEAPSORT)
1257 static int sort_qsort(void *list, size_t count, size_t elem_size,
1258 int (*cmp_func)(const void *, const void *))
1261 qsort(list, count, elem_size, cmp_func);
1266 * Sort list of lines and writes it to the file
1269 sort_list_to_file(struct sort_list *list, const char *outfile)
1271 struct sort_mods *sm = &(keys[0].sm);
1273 if (!(sm->Mflag) && !(sm->Rflag) && !(sm->Vflag) && !(sm->Vflag) &&
1274 !(sm->gflag) && !(sm->hflag) && !(sm->nflag)) {
1275 if ((sort_opts_vals.sort_method == SORT_DEFAULT) && byte_sort)
1276 sort_opts_vals.sort_method = SORT_RADIXSORT;
1278 } else if (sort_opts_vals.sort_method == SORT_RADIXSORT)
1279 err(2, "%s", getstr(9));
1282 * to handle stable sort and the unique cases in the
1283 * right order, we need stable basic algorithm
1285 if (sort_opts_vals.sflag) {
1286 switch (sort_opts_vals.sort_method){
1287 case SORT_MERGESORT:
1289 case SORT_RADIXSORT:
1292 sort_opts_vals.sort_method = SORT_MERGESORT;
1295 errx(2, "%s", getstr(10));
1299 if (sort_opts_vals.sort_method == SORT_DEFAULT)
1300 sort_opts_vals.sort_method = DEFAULT_SORT_ALGORITHM;
1303 printf("sort_method=%s\n",
1304 get_sort_method_name(sort_opts_vals.sort_method));
1306 switch (sort_opts_vals.sort_method){
1307 case SORT_RADIXSORT:
1308 rxsort(list->list, list->count);
1309 sort_list_dump(list, outfile);
1311 case SORT_MERGESORT:
1312 mt_sort(list, mergesort, outfile);
1315 mt_sort(list, heapsort, outfile);
1318 mt_sort(list, sort_qsort, outfile);
1321 mt_sort(list, DEFAULT_SORT_FUNC, outfile);
1326 /******************* MT SORT ************************/
1328 #if defined(SORT_THREADS)
1329 /* semaphore to count threads */
1332 /* current system sort function */
1333 static int (*g_sort_func)(void *, size_t, size_t,
1334 int(*)(const void *, const void *));
1337 * Sort cycle thread (in multi-threaded mode)
1340 mt_sort_thread(void* arg)
1342 struct sort_list *list = arg;
1344 g_sort_func(list->list, list->count, sizeof(struct sort_list_item *),
1345 (int(*)(const void *, const void *)) list_coll);
1353 * Compare sub-lists. Empty sub-lists always go to the end of the list.
1356 sub_list_cmp(struct sort_list *l1, struct sort_list *l2)
1362 if (l1->count == 0) {
1363 return ((l2->count == 0) ? 0 : +1);
1364 } else if (l2->count == 0) {
1369 ret = list_coll(&(l1->list[0]), &(l2->list[0]));
1371 return ((l1->sub_list_pos < l2->sub_list_pos) ?
1379 * Swap two array elements
1382 sub_list_swap(struct sort_list **sl, int i1, int i2)
1384 struct sort_list *tmp;
1391 /* heap algorithm ==>> */
1394 * See heap sort algorithm
1395 * "Raises" last element to its right place
1398 sub_list_swim(struct sort_list **sl, int indx)
1404 parent_index = (indx - 1) >> 1;
1406 if (sub_list_cmp(sl[indx], sl[parent_index]) < 0) {
1407 /* swap child and parent and continue */
1408 sub_list_swap(sl, indx, parent_index);
1409 sub_list_swim(sl, parent_index);
1415 * Sink the top element to its correct position
1418 sub_list_sink(struct sort_list **sl, int indx, int size)
1420 int left_child_index;
1421 int right_child_index;
1423 left_child_index = indx + indx + 1;
1424 right_child_index = left_child_index + 1;
1426 if (left_child_index < size) {
1427 int min_child_index;
1429 min_child_index = left_child_index;
1431 if ((right_child_index < size) &&
1432 (sub_list_cmp(sl[left_child_index],
1433 sl[right_child_index]) > 0))
1434 min_child_index = right_child_index;
1435 if (sub_list_cmp(sl[indx], sl[min_child_index]) > 0) {
1436 sub_list_swap(sl, indx, min_child_index);
1437 sub_list_sink(sl, min_child_index, size);
1442 /* <<== heap algorithm */
1445 * Adds element to the "right" end
1448 sub_list_push(struct sort_list *s, struct sort_list **sl, int size)
1452 sub_list_swim(sl, size - 1);
1455 struct last_printed_item
1457 struct sort_list_item *item;
1461 * Prints the current line of the file
1464 sub_list_header_print(struct sort_list *sl, FILE *f_out,
1465 struct last_printed_item *lp)
1468 if (sl && sl->count && f_out && sl->list[0]->str) {
1469 if (sort_opts_vals.uflag) {
1470 if ((lp->item == NULL) || (list_coll(&(lp->item),
1472 bwsfwrite(sl->list[0]->str, f_out,
1473 sort_opts_vals.zflag);
1474 lp->item = sl->list[0];
1477 bwsfwrite(sl->list[0]->str, f_out,
1478 sort_opts_vals.zflag);
1486 sub_list_next(struct sort_list *sl)
1489 if (sl && sl->count) {
1496 * Merge sub-lists to a file
1499 merge_sub_lists(struct sort_list **sl, size_t n, FILE* f_out)
1501 struct last_printed_item lp;
1504 memset(&lp,0,sizeof(lp));
1506 /* construct the initial list: */
1507 for (i = 0; i < n; i++)
1508 sub_list_push(sl[i], sl, i);
1510 while (sl[0]->count) { /* unfinished lists are always in front */
1511 /* output the smallest line: */
1512 sub_list_header_print(sl[0], f_out, &lp);
1513 /* move to a new line, if possible: */
1514 sub_list_next(sl[0]);
1515 /* re-arrange the list: */
1516 sub_list_sink(sl, 0, n);
1521 * Merge sub-lists to a file
1524 merge_list_parts(struct sort_list **parts, size_t n, const char *fn)
1528 f_out = openfile(fn,"w");
1530 merge_sub_lists(parts, n, f_out);
1532 closefile(f_out, fn);
1535 #endif /* defined(SORT_THREADS) */
1537 * Multi-threaded sort algorithm "driver"
1540 mt_sort(struct sort_list *list,
1541 int(*sort_func)(void *, size_t, size_t, int(*)(const void *, const void *)),
1544 #if defined(SORT_THREADS)
1545 if (nthreads < 2 || list->count < MT_SORT_THRESHOLD) {
1546 size_t nthreads_save = nthreads;
1549 /* if single thread or small data, do simple sort */
1550 sort_func(list->list, list->count,
1551 sizeof(struct sort_list_item *),
1552 (int(*)(const void *, const void *)) list_coll);
1553 sort_list_dump(list, fn);
1554 #if defined(SORT_THREADS)
1555 nthreads = nthreads_save;
1557 /* multi-threaded sort */
1558 struct sort_list **parts;
1559 size_t avgsize, cstart, i;
1561 /* array of sub-lists */
1562 parts = sort_malloc(sizeof(struct sort_list*) * nthreads);
1564 avgsize = list->count / nthreads;
1566 /* set global system sort function */
1567 g_sort_func = sort_func;
1570 for (i = 0; i < nthreads; ++i) {
1573 parts[i] = sort_malloc(sizeof(struct sort_list));
1574 parts[i]->list = list->list + cstart;
1575 parts[i]->memsize = 0;
1576 parts[i]->sub_list_pos = i;
1578 sz = (i == nthreads - 1) ? list->count - cstart :
1581 parts[i]->count = sz;
1583 parts[i]->size = parts[i]->count;
1588 /* init threads counting semaphore */
1589 sem_init(&mtsem, 0, 0);
1592 for (i = 0; i < nthreads; ++i) {
1594 pthread_attr_t attr;
1596 pthread_attr_init(&attr);
1597 pthread_attr_setdetachstate(&attr, PTHREAD_DETACHED);
1600 int res = pthread_create(&pth, &attr,
1601 mt_sort_thread, parts[i]);
1605 if (errno == EAGAIN) {
1612 pthread_attr_destroy(&attr);
1615 /* wait for threads completion */
1616 for (i = 0; i < nthreads; ++i) {
1619 /* destroy the semaphore - we do not need it anymore */
1620 sem_destroy(&mtsem);
1622 /* merge sorted sub-lists to the file */
1623 merge_list_parts(parts, nthreads, fn);
1625 /* free sub-lists data */
1626 for (i = 0; i < nthreads; ++i) {
1627 sort_free(parts[i]);
1631 #endif /* defined(SORT_THREADS) */