2 * SPDX-License-Identifier: BSD-2-Clause
4 * Copyright (C) 2009 Gabor Kovesdan <gabor@FreeBSD.org>
5 * Copyright (C) 2012 Oleg Moskalenko <mom040267@gmail.com>
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 #include <sys/cdefs.h>
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 * File reader structure
71 unsigned char *mmapaddr;
72 unsigned char *mmapptr;
80 * Structure to be used in file merge process.
84 struct file_reader *fr;
85 struct sort_list_item *si; /* current top line */
90 * List elements of "cleanable" files list.
95 LIST_ENTRY(CLEANABLE_FILE) files;
99 * List header of "cleanable" files list.
101 static LIST_HEAD(CLEANABLE_FILES,CLEANABLE_FILE) tmp_files;
104 * Semaphore to protect the tmp file list.
105 * We use semaphore here because it is signal-safe, according to POSIX.
106 * And semaphore does not require pthread library.
108 static sem_t tmp_files_sem;
110 static void mt_sort(struct sort_list *list,
111 int (*sort_func)(void *, size_t, size_t,
112 int (*)(const void *, const void *)), const char* fn);
115 * Init tmp files list
121 LIST_INIT(&tmp_files);
122 sem_init(&tmp_files_sem, 0, 1);
126 * Save name of a tmp file for signal cleanup
129 tmp_file_atexit(const char *tmp_file)
133 sem_wait(&tmp_files_sem);
134 struct CLEANABLE_FILE *item =
135 sort_malloc(sizeof(struct CLEANABLE_FILE));
136 item->fn = sort_strdup(tmp_file);
137 LIST_INSERT_HEAD(&tmp_files, item, files);
138 sem_post(&tmp_files_sem);
146 clear_tmp_files(void)
148 struct CLEANABLE_FILE *item;
150 sem_wait(&tmp_files_sem);
151 LIST_FOREACH(item,&tmp_files,files) {
152 if ((item) && (item->fn))
155 sem_post(&tmp_files_sem);
159 * Check whether a file is a temporary file
162 file_is_tmp(const char* fn)
164 struct CLEANABLE_FILE *item;
168 sem_wait(&tmp_files_sem);
169 LIST_FOREACH(item,&tmp_files,files) {
170 if ((item) && (item->fn))
171 if (strcmp(item->fn, fn) == 0) {
176 sem_post(&tmp_files_sem);
183 * Generate new temporary file name
186 new_tmp_file_name(void)
191 if (asprintf(&ret, "%s/.bsdsort.XXXXXXXXXX", tmpdir) == -1)
192 err(2, "asprintf()");
193 if ((fd = mkstemp(ret)) == -1)
197 tmp_file_atexit(ret);
202 * Initialize file list
205 file_list_init(struct file_list *fl, bool tmp)
209 memset(fl, 0, sizeof(*fl));
215 * Add a file name to the list
218 file_list_add(struct file_list *fl, const char *fn, bool allocate)
222 if (fl->count >= fl->sz || (fl->fns == NULL)) {
223 fl->sz = (fl->sz) * 2 + 1;
224 fl->fns = sort_realloc(fl->fns, fl->sz *
227 fl->fns[fl->count] = allocate ? sort_strdup(fn) : fn;
233 * Populate file list from array of file names
236 file_list_populate(struct file_list *fl, int argc, char **argv, bool allocate)
242 for (i = 0; i < argc; i++)
243 file_list_add(fl, argv[i], allocate);
248 * Clean file list data and delete the files,
249 * if this is a list of temporary files
252 file_list_clean(struct file_list *fl)
259 for (i = 0; i < fl->count; i++) {
263 sort_free(fl->fns[i]);
280 sort_list_init(struct sort_list *l)
284 memset(l, 0, sizeof(*l));
285 l->memsize = sizeof(struct sort_list);
290 * Add string to sort list
293 sort_list_add(struct sort_list *l, struct bwstring *str)
297 size_t indx = l->count;
299 if ((l->list == NULL) || (indx >= l->size)) {
300 size_t newsize = (l->size + 1) + 1024;
302 l->list = sort_realloc(l->list,
303 sizeof(struct sort_list_item*) * newsize);
304 l->memsize += (newsize - l->size) *
305 sizeof(struct sort_list_item*);
308 l->list[indx] = sort_list_item_alloc();
309 sort_list_item_set(l->list[indx], str);
310 l->memsize += sort_list_item_size(l->list[indx]);
316 * Clean sort list data
319 sort_list_clean(struct sort_list *l)
326 for (i = 0; i < l->count; i++) {
327 struct sort_list_item *item;
332 sort_list_item_clean(item);
342 l->memsize = sizeof(struct sort_list);
347 * Write sort list to file
350 sort_list_dump(struct sort_list *l, const char *fn)
356 f = openfile(fn, "w");
362 if (!(sort_opts_vals.uflag)) {
363 for (i = 0; i < l->count; ++i)
364 bwsfwrite(l->list[i]->str, f,
365 sort_opts_vals.zflag);
367 struct sort_list_item *last_printed_item = NULL;
368 struct sort_list_item *item;
369 for (i = 0; i < l->count; ++i) {
371 if ((last_printed_item == NULL) ||
372 list_coll(&last_printed_item, &item)) {
373 bwsfwrite(item->str, f, sort_opts_vals.zflag);
374 last_printed_item = item;
385 * Checks if the given file is sorted. Stops at the first disorder,
386 * prints the disordered line and returns 1.
389 check(const char *fn)
391 struct bwstring *s1, *s2, *s1disorder, *s2disorder;
392 struct file_reader *fr;
393 struct keys_array *ka1, *ka2;
395 size_t pos, posdisorder;
397 s1 = s2 = s1disorder = s2disorder = NULL;
400 fr = file_reader_init(fn);
411 s1 = file_reader_readline(fr);
415 ka1 = keys_array_alloc();
418 s2 = file_reader_readline(fr);
422 ka2 = keys_array_alloc();
428 bwsprintf(stdout, s2, "s1=<", ">");
429 bwsprintf(stdout, s1, "s2=<", ">");
431 int cmp = key_coll(ka2, ka1, 0);
433 printf("; cmp1=%d", cmp);
435 if (!cmp && sort_opts_vals.complex_sort &&
436 !(sort_opts_vals.uflag) && !(sort_opts_vals.sflag)) {
437 cmp = top_level_str_coll(s2, s1);
439 printf("; cmp2=%d", cmp);
444 if ((sort_opts_vals.uflag && (cmp <= 0)) || (cmp < 0)) {
445 if (!(sort_opts_vals.csilentflag)) {
446 s2disorder = bwsdup(s2);
449 s1disorder = bwsdup(s1);
457 clean_keys_array(s1, ka1);
465 s2 = file_reader_readline(fr);
469 ka2 = keys_array_alloc();
475 clean_keys_array(s1, ka1);
483 clean_keys_array(s2, ka2);
490 if ((fn == NULL) || (*fn == 0) || (strcmp(fn, "-") == 0)) {
492 s2 = file_reader_readline(fr);
499 file_reader_free(fr);
502 bws_disorder_warnx(s2disorder, fn, posdisorder);
504 bws_disorder_warnx(s1disorder, fn, posdisorder);
505 if (s1disorder != s2disorder)
520 * Opens a file. If the given filename is "-", stdout will be
524 openfile(const char *fn, const char *mode)
528 if (strcmp(fn, "-") == 0)
529 return ((mode && mode[0] == 'r') ? stdin : stdout);
531 mode_t orig_file_mask = 0;
532 int is_tmp = file_is_tmp(fn);
534 if (is_tmp && (mode[0] == 'w'))
535 orig_file_mask = umask(S_IWGRP | S_IWOTH |
538 if (is_tmp && (compress_program != NULL)) {
545 r = asprintf(&cmd, "cat %s | %s -d",
546 fn, compress_program);
547 else if (mode[0] == 'w')
548 r = asprintf(&cmd, "%s > %s",
549 compress_program, fn);
551 err(2, "%s", getstr(7));
554 err(2, "aspritnf()");
556 if ((file = popen(cmd, mode)) == NULL)
560 if ((file = fopen(fn, mode)) == NULL)
563 if (is_tmp && (mode[0] == 'w'))
564 umask(orig_file_mask);
573 closefile(FILE *f, const char *fn)
575 if (f == NULL || f == stdin)
581 if (file_is_tmp(fn) && compress_program != NULL) {
589 * Reads a file into the internal buffer.
592 file_reader_init(const char *fsrc)
594 struct file_reader *ret;
599 ret = sort_calloc(1, sizeof(struct file_reader));
601 ret->elsymb = sort_opts_vals.zflag ? '\0' : '\n';
602 ret->fname = sort_strdup(fsrc);
604 if (strcmp(fsrc, "-") && (compress_program == NULL) && use_mmap) {
607 struct stat stat_buf;
612 flags = MAP_NOCORE | MAP_NOSYNC;
614 fd = open(fsrc, O_RDONLY);
618 if (fstat(fd, &stat_buf) < 0) {
623 sz = stat_buf.st_size;
625 #if defined(MAP_PREFAULT_READ)
626 flags |= MAP_PREFAULT_READ;
629 addr = mmap(NULL, sz, PROT_READ, flags, fd, 0);
630 if (addr == MAP_FAILED) {
636 ret->mmapaddr = addr;
638 ret->mmapptr = ret->mmapaddr;
643 if (ret->mmapaddr == NULL) {
644 ret->file = openfile(fsrc, "r");
645 if (ret->file == NULL)
653 file_reader_readline(struct file_reader *fr)
655 struct bwstring *ret = NULL;
658 unsigned char *mmapend;
660 mmapend = fr->mmapaddr + fr->mmapsize;
661 if (fr->mmapptr >= mmapend)
664 unsigned char *strend;
667 sz = mmapend - fr->mmapptr;
668 strend = memchr(fr->mmapptr, fr->elsymb, sz);
670 if (strend == NULL) {
671 ret = bwscsbdup(fr->mmapptr, sz);
672 fr->mmapptr = mmapend;
674 ret = bwscsbdup(fr->mmapptr, strend -
676 fr->mmapptr = strend + 1;
682 len = getdelim(&fr->buffer, &fr->bsz, fr->elsymb, fr->file);
688 if (len > 0 && fr->buffer[len - 1] == fr->elsymb)
690 ret = bwscsbdup(fr->buffer, len);
697 file_reader_clean(struct file_reader *fr)
704 munmap(fr->mmapaddr, fr->mmapsize);
709 closefile(fr->file, fr->fname);
711 memset(fr, 0, sizeof(struct file_reader));
715 file_reader_free(struct file_reader *fr)
720 file_reader_clean(fr);
725 procfile(const char *fsrc, struct sort_list *list, struct file_list *fl)
727 struct file_reader *fr;
729 fr = file_reader_init(fsrc);
733 /* file browse cycle */
735 struct bwstring *bws;
737 bws = file_reader_readline(fr);
742 sort_list_add(list, bws);
744 if (list->memsize >= available_free_memory) {
747 fn = new_tmp_file_name();
748 sort_list_to_file(list, fn);
749 file_list_add(fl, fn, false);
750 sort_list_clean(list);
754 file_reader_free(fr);
760 * Compare file headers. Files with EOF always go to the end of the list.
763 file_header_cmp(struct file_header *f1, struct file_header *f2)
769 if (f1->fr == NULL) {
770 return ((f2->fr == NULL) ? 0 : +1);
771 } else if (f2->fr == NULL)
776 ret = list_coll(&(f1->si), &(f2->si));
778 return ((f1->file_pos < f2->file_pos) ? -1 : +1);
785 * Allocate and init file header structure
788 file_header_init(struct file_header **fh, const char *fn, size_t file_pos)
792 struct bwstring *line;
794 *fh = sort_malloc(sizeof(struct file_header));
795 (*fh)->file_pos = file_pos;
796 (*fh)->fr = file_reader_init(fn);
797 if ((*fh)->fr == NULL) {
799 err(2, "%s", getstr(8));
801 line = file_reader_readline((*fh)->fr);
803 file_reader_free((*fh)->fr);
807 (*fh)->si = sort_list_item_alloc();
808 sort_list_item_set((*fh)->si, line);
817 file_header_close(struct file_header **fh)
821 file_reader_free((*fh)->fr);
824 sort_list_item_clean((*fh)->si);
825 sort_free((*fh)->si);
834 * Swap two array elements
837 file_header_swap(struct file_header **fh, size_t i1, size_t i2)
839 struct file_header *tmp;
846 /* heap algorithm ==>> */
849 * See heap sort algorithm
850 * "Raises" last element to its right place
853 file_header_heap_swim(struct file_header **fh, size_t indx)
859 parent_index = (indx - 1) >> 1;
861 if (file_header_cmp(fh[indx], fh[parent_index]) < 0) {
862 /* swap child and parent and continue */
863 file_header_swap(fh, indx, parent_index);
864 file_header_heap_swim(fh, parent_index);
870 * Sink the top element to its correct position
873 file_header_heap_sink(struct file_header **fh, size_t indx, size_t size)
875 size_t left_child_index;
876 size_t right_child_index;
878 left_child_index = indx + indx + 1;
879 right_child_index = left_child_index + 1;
881 if (left_child_index < size) {
882 size_t min_child_index;
884 min_child_index = left_child_index;
886 if ((right_child_index < size) &&
887 (file_header_cmp(fh[left_child_index],
888 fh[right_child_index]) > 0))
889 min_child_index = right_child_index;
890 if (file_header_cmp(fh[indx], fh[min_child_index]) > 0) {
891 file_header_swap(fh, indx, min_child_index);
892 file_header_heap_sink(fh, min_child_index, size);
897 /* <<== heap algorithm */
900 * Adds element to the "left" end
903 file_header_list_rearrange_from_header(struct file_header **fh, size_t size)
906 file_header_heap_sink(fh, 0, size);
910 * Adds element to the "right" end
913 file_header_list_push(struct file_header *f, struct file_header **fh, size_t size)
917 file_header_heap_swim(fh, size - 1);
922 struct bwstring *str;
926 * Prints the current line of the file
929 file_header_print(struct file_header *fh, FILE *f_out, struct last_printed *lp)
932 if (fh && fh->fr && f_out && fh->si && fh->si->str) {
933 if (sort_opts_vals.uflag) {
934 if ((lp->str == NULL) || (str_list_coll(lp->str, &(fh->si)))) {
935 bwsfwrite(fh->si->str, f_out, sort_opts_vals.zflag);
938 lp->str = bwsdup(fh->si->str);
941 bwsfwrite(fh->si->str, f_out, sort_opts_vals.zflag);
949 file_header_read_next(struct file_header *fh)
953 struct bwstring *tmp;
955 tmp = file_reader_readline(fh->fr);
957 file_reader_free(fh->fr);
960 sort_list_item_clean(fh->si);
966 fh->si = sort_list_item_alloc();
967 sort_list_item_set(fh->si, tmp);
973 * Merge array of "files headers"
976 file_headers_merge(size_t fnum, struct file_header **fh, FILE *f_out)
978 struct last_printed lp;
981 memset(&lp, 0, sizeof(lp));
984 * construct the initial sort structure
986 for (i = 0; i < fnum; i++)
987 file_header_list_push(fh[i], fh, i);
989 while (fh[0]->fr) { /* unfinished files are always in front */
990 /* output the smallest line: */
991 file_header_print(fh[0], f_out, &lp);
992 /* read a new line, if possible: */
993 file_header_read_next(fh[0]);
994 /* re-arrange the list: */
995 file_header_list_rearrange_from_header(fh, fnum);
1003 * Merges the given files into the output file, which can be
1007 merge_files_array(size_t argc, const char **argv, const char *fn_out)
1010 if (argv && fn_out) {
1011 struct file_header **fh;
1015 f_out = openfile(fn_out, "w");
1020 fh = sort_malloc((argc + 1) * sizeof(struct file_header *));
1022 for (i = 0; i < argc; i++)
1023 file_header_init(fh + i, argv[i], (size_t) i);
1025 file_headers_merge(argc, fh, f_out);
1027 for (i = 0; i < argc; i++)
1028 file_header_close(fh + i);
1032 closefile(f_out, fn_out);
1037 * Shrinks the file list until its size smaller than max number of opened files
1040 shrink_file_list(struct file_list *fl)
1043 if ((fl == NULL) || (size_t) (fl->count) < max_open_files)
1046 struct file_list new_fl;
1049 file_list_init(&new_fl, true);
1050 while (indx < fl->count) {
1054 num = fl->count - indx;
1055 fnew = new_tmp_file_name();
1057 if ((size_t) num >= max_open_files)
1058 num = max_open_files - 1;
1059 merge_files_array(num, fl->fns + indx, fnew);
1063 for (i = 0; i < num; i++)
1064 unlink(fl->fns[indx + i]);
1066 file_list_add(&new_fl, fnew, false);
1069 fl->tmp = false; /* already taken care of */
1070 file_list_clean(fl);
1072 fl->count = new_fl.count;
1073 fl->fns = new_fl.fns;
1075 fl->tmp = new_fl.tmp;
1082 * Merge list of files
1085 merge_files(struct file_list *fl, const char *fn_out)
1089 while (shrink_file_list(fl));
1091 merge_files_array(fl->count, fl->fns, fn_out);
1096 get_sort_method_name(int sm)
1099 if (sm == SORT_MERGESORT)
1101 else if (sort_opts_vals.sort_method == SORT_RADIXSORT)
1103 else if (sort_opts_vals.sort_method == SORT_HEAPSORT)
1112 static int sort_qsort(void *list, size_t count, size_t elem_size,
1113 int (*cmp_func)(const void *, const void *))
1116 qsort(list, count, elem_size, cmp_func);
1121 * Sort list of lines and writes it to the file
1124 sort_list_to_file(struct sort_list *list, const char *outfile)
1126 struct sort_mods *sm = &(keys[0].sm);
1128 if (!(sm->Mflag) && !(sm->Rflag) && !(sm->Vflag) &&
1129 !(sm->gflag) && !(sm->hflag) && !(sm->nflag)) {
1130 if ((sort_opts_vals.sort_method == SORT_DEFAULT) && byte_sort)
1131 sort_opts_vals.sort_method = SORT_RADIXSORT;
1133 } else if (sort_opts_vals.sort_method == SORT_RADIXSORT)
1134 err(2, "%s", getstr(9));
1137 * to handle stable sort and the unique cases in the
1138 * right order, we need stable basic algorithm
1140 if (sort_opts_vals.sflag) {
1141 switch (sort_opts_vals.sort_method){
1142 case SORT_MERGESORT:
1144 case SORT_RADIXSORT:
1147 sort_opts_vals.sort_method = SORT_MERGESORT;
1150 errx(2, "%s", getstr(10));
1154 if (sort_opts_vals.sort_method == SORT_DEFAULT)
1155 sort_opts_vals.sort_method = DEFAULT_SORT_ALGORITHM;
1158 printf("sort_method=%s\n",
1159 get_sort_method_name(sort_opts_vals.sort_method));
1161 switch (sort_opts_vals.sort_method){
1162 case SORT_RADIXSORT:
1163 rxsort(list->list, list->count);
1164 sort_list_dump(list, outfile);
1166 case SORT_MERGESORT:
1167 mt_sort(list, mergesort, outfile);
1170 mt_sort(list, heapsort, outfile);
1173 mt_sort(list, sort_qsort, outfile);
1176 mt_sort(list, DEFAULT_SORT_FUNC, outfile);
1181 /******************* MT SORT ************************/
1183 #if defined(SORT_THREADS)
1184 /* semaphore to count threads */
1187 /* current system sort function */
1188 static int (*g_sort_func)(void *, size_t, size_t,
1189 int(*)(const void *, const void *));
1192 * Sort cycle thread (in multi-threaded mode)
1195 mt_sort_thread(void* arg)
1197 struct sort_list *list = arg;
1199 g_sort_func(list->list, list->count, sizeof(struct sort_list_item *),
1200 (int(*)(const void *, const void *)) list_coll);
1208 * Compare sub-lists. Empty sub-lists always go to the end of the list.
1211 sub_list_cmp(struct sort_list *l1, struct sort_list *l2)
1217 if (l1->count == 0) {
1218 return ((l2->count == 0) ? 0 : +1);
1219 } else if (l2->count == 0) {
1224 ret = list_coll(&(l1->list[0]), &(l2->list[0]));
1226 return ((l1->sub_list_pos < l2->sub_list_pos) ?
1234 * Swap two array elements
1237 sub_list_swap(struct sort_list **sl, size_t i1, size_t i2)
1239 struct sort_list *tmp;
1246 /* heap algorithm ==>> */
1249 * See heap sort algorithm
1250 * "Raises" last element to its right place
1253 sub_list_swim(struct sort_list **sl, size_t indx)
1257 size_t parent_index;
1259 parent_index = (indx - 1) >> 1;
1261 if (sub_list_cmp(sl[indx], sl[parent_index]) < 0) {
1262 /* swap child and parent and continue */
1263 sub_list_swap(sl, indx, parent_index);
1264 sub_list_swim(sl, parent_index);
1270 * Sink the top element to its correct position
1273 sub_list_sink(struct sort_list **sl, size_t indx, size_t size)
1275 size_t left_child_index;
1276 size_t right_child_index;
1278 left_child_index = indx + indx + 1;
1279 right_child_index = left_child_index + 1;
1281 if (left_child_index < size) {
1282 size_t min_child_index;
1284 min_child_index = left_child_index;
1286 if ((right_child_index < size) &&
1287 (sub_list_cmp(sl[left_child_index],
1288 sl[right_child_index]) > 0))
1289 min_child_index = right_child_index;
1290 if (sub_list_cmp(sl[indx], sl[min_child_index]) > 0) {
1291 sub_list_swap(sl, indx, min_child_index);
1292 sub_list_sink(sl, min_child_index, size);
1297 /* <<== heap algorithm */
1300 * Adds element to the "right" end
1303 sub_list_push(struct sort_list *s, struct sort_list **sl, size_t size)
1307 sub_list_swim(sl, size - 1);
1310 struct last_printed_item
1312 struct sort_list_item *item;
1316 * Prints the current line of the file
1319 sub_list_header_print(struct sort_list *sl, FILE *f_out,
1320 struct last_printed_item *lp)
1323 if (sl && sl->count && f_out && sl->list[0]->str) {
1324 if (sort_opts_vals.uflag) {
1325 if ((lp->item == NULL) || (list_coll(&(lp->item),
1327 bwsfwrite(sl->list[0]->str, f_out,
1328 sort_opts_vals.zflag);
1329 lp->item = sl->list[0];
1332 bwsfwrite(sl->list[0]->str, f_out,
1333 sort_opts_vals.zflag);
1341 sub_list_next(struct sort_list *sl)
1344 if (sl && sl->count) {
1351 * Merge sub-lists to a file
1354 merge_sub_lists(struct sort_list **sl, size_t n, FILE* f_out)
1356 struct last_printed_item lp;
1359 memset(&lp,0,sizeof(lp));
1361 /* construct the initial list: */
1362 for (i = 0; i < n; i++)
1363 sub_list_push(sl[i], sl, i);
1365 while (sl[0]->count) { /* unfinished lists are always in front */
1366 /* output the smallest line: */
1367 sub_list_header_print(sl[0], f_out, &lp);
1368 /* move to a new line, if possible: */
1369 sub_list_next(sl[0]);
1370 /* re-arrange the list: */
1371 sub_list_sink(sl, 0, n);
1376 * Merge sub-lists to a file
1379 merge_list_parts(struct sort_list **parts, size_t n, const char *fn)
1383 f_out = openfile(fn,"w");
1385 merge_sub_lists(parts, n, f_out);
1387 closefile(f_out, fn);
1390 #endif /* defined(SORT_THREADS) */
1392 * Multi-threaded sort algorithm "driver"
1395 mt_sort(struct sort_list *list,
1396 int(*sort_func)(void *, size_t, size_t, int(*)(const void *, const void *)),
1399 #if defined(SORT_THREADS)
1400 if (nthreads < 2 || list->count < MT_SORT_THRESHOLD) {
1401 size_t nthreads_save = nthreads;
1404 /* if single thread or small data, do simple sort */
1405 sort_func(list->list, list->count,
1406 sizeof(struct sort_list_item *),
1407 (int(*)(const void *, const void *)) list_coll);
1408 sort_list_dump(list, fn);
1409 #if defined(SORT_THREADS)
1410 nthreads = nthreads_save;
1412 /* multi-threaded sort */
1413 struct sort_list **parts;
1414 size_t avgsize, cstart, i;
1416 /* array of sub-lists */
1417 parts = sort_malloc(sizeof(struct sort_list*) * nthreads);
1419 avgsize = list->count / nthreads;
1421 /* set global system sort function */
1422 g_sort_func = sort_func;
1425 for (i = 0; i < nthreads; ++i) {
1428 parts[i] = sort_malloc(sizeof(struct sort_list));
1429 parts[i]->list = list->list + cstart;
1430 parts[i]->memsize = 0;
1431 parts[i]->sub_list_pos = i;
1433 sz = (i == nthreads - 1) ? list->count - cstart :
1436 parts[i]->count = sz;
1438 parts[i]->size = parts[i]->count;
1443 /* init threads counting semaphore */
1444 sem_init(&mtsem, 0, 0);
1447 for (i = 0; i < nthreads; ++i) {
1449 pthread_attr_t attr;
1451 pthread_attr_init(&attr);
1452 pthread_attr_setdetachstate(&attr, PTHREAD_DETACHED);
1455 int res = pthread_create(&pth, &attr,
1456 mt_sort_thread, parts[i]);
1460 if (errno == EAGAIN) {
1467 pthread_attr_destroy(&attr);
1470 /* wait for threads completion */
1471 for (i = 0; i < nthreads; ++i) {
1474 /* destroy the semaphore - we do not need it anymore */
1475 sem_destroy(&mtsem);
1477 /* merge sorted sub-lists to the file */
1478 merge_list_parts(parts, nthreads, fn);
1480 /* free sub-lists data */
1481 for (i = 0; i < nthreads; ++i) {
1482 sort_free(parts[i]);
1486 #endif /* defined(SORT_THREADS) */