1 /*-
2  * SPDX-License-Identifier: BSD-2-Clause
105  * We use semaphore here because it is signal-safe, according to POSIX.
136 		item->fn = sort_strdup(tmp_file);  in tmp_file_atexit()
152 		if ((item) && (item->fn))  in clear_tmp_files()
153 			unlink(item->fn);  in clear_tmp_files()
170 			if ((item) && (item->fn))  in file_is_tmp()
171 				if (strcmp(item->fn, fn) == 0) {  in file_is_tmp()
191 	if (asprintf(&ret, "%s/.bsdsort.XXXXXXXXXX", tmpdir) == -1)  in new_tmp_file_name()
193 	if ((fd = mkstemp(ret)) == -1)  in new_tmp_file_name()
210 		fl->tmp = tmp;  in file_list_init()
222 		if (fl->count >= fl->sz || (fl->fns == NULL)) {  in file_list_add()
223 			fl->sz = (fl->sz) * 2 + 1;  in file_list_add()
224 			fl->fns = sort_realloc(fl->fns, fl->sz *  in file_list_add()
227 		fl->fns[fl->count] = allocate ? sort_strdup(fn) : fn;  in file_list_add()
228 		fl->count += 1;  in file_list_add()
256 		if (fl->fns) {  in file_list_clean()
259 			for (i = 0; i < fl->count; i++) {  in file_list_clean()
260 				if (fl->fns[i]) {  in file_list_clean()
261 					if (fl->tmp)  in file_list_clean()
262 						unlink(fl->fns[i]);  in file_list_clean()
263 					sort_free(fl->fns[i]);  in file_list_clean()
264 					fl->fns[i] = 0;  in file_list_clean()
267 			sort_free(fl->fns);  in file_list_clean()
268 			fl->fns = NULL;  in file_list_clean()
270 		fl->sz = 0;  in file_list_clean()
271 		fl->count = 0;  in file_list_clean()
272 		fl->tmp = false;  in file_list_clean()
285 		l->memsize = sizeof(struct sort_list);  in sort_list_init()
297 		size_t indx = l->count;  in sort_list_add()
299 		if ((l->list == NULL) || (indx >= l->size)) {  in sort_list_add()
300 			size_t newsize = (l->size + 1) + 1024;  in sort_list_add()
302 			l->list = sort_realloc(l->list,  in sort_list_add()
304 			l->memsize += (newsize - l->size) *  in sort_list_add()
306 			l->size = newsize;  in sort_list_add()
308 		l->list[indx] = sort_list_item_alloc();  in sort_list_add()
309 		sort_list_item_set(l->list[indx], str);  in sort_list_add()
310 		l->memsize += sort_list_item_size(l->list[indx]);  in sort_list_add()
311 		l->count += 1;  in sort_list_add()
323 		if (l->list) {  in sort_list_clean()
326 			for (i = 0; i < l->count; i++) {  in sort_list_clean()
329 				item = l->list[i];  in sort_list_clean()
334 					l->list[i] = NULL;  in sort_list_clean()
337 			sort_free(l->list);  in sort_list_clean()
338 			l->list = NULL;  in sort_list_clean()
340 		l->count = 0;  in sort_list_clean()
341 		l->size = 0;  in sort_list_clean()
342 		l->memsize = sizeof(struct sort_list);  in sort_list_clean()
360 		if (l->list) {  in sort_list_dump()
363 				for (i = 0; i < l->count; ++i)  in sort_list_dump()
364 					bwsfwrite(l->list[i]->str, f,  in sort_list_dump()
369 				for (i = 0; i < l->count; ++i) {  in sort_list_dump()
370 					item = l->list[i];  in sort_list_dump()
373 						bwsfwrite(item->str, f, sort_opts_vals.zflag);  in sort_list_dump()
490 	if ((fn == NULL) || (*fn == 0) || (strcmp(fn, "-") == 0)) {  in check()
520  * Opens a file.  If the given filename is "-", stdout will be
528 	if (strcmp(fn, "-") == 0)  in openfile()
545 			r = asprintf(&cmd, "cat %s | %s -d",  in openfile()
553 		if (r == -1)  in openfile()
597 		fsrc = "-";  in file_reader_init()
601 	ret->elsymb = sort_opts_vals.zflag ? '\0' : '\n';  in file_reader_init()
602 	ret->fname = sort_strdup(fsrc);  in file_reader_init()
604 	if (strcmp(fsrc, "-") && (compress_program == NULL) && use_mmap) {  in file_reader_init()
635 			ret->fd = fd;  in file_reader_init()
636 			ret->mmapaddr = addr;  in file_reader_init()
637 			ret->mmapsize = sz;  in file_reader_init()
638 			ret->mmapptr = ret->mmapaddr;  in file_reader_init()
643 	if (ret->mmapaddr == NULL) {  in file_reader_init()
644 		ret->file = openfile(fsrc, "r");  in file_reader_init()
645 		if (ret->file == NULL)  in file_reader_init()
657 	if (fr->mmapaddr) {  in file_reader_readline()
660 		mmapend = fr->mmapaddr + fr->mmapsize;  in file_reader_readline()
661 		if (fr->mmapptr >= mmapend)  in file_reader_readline()
667 			sz = mmapend - fr->mmapptr;  in file_reader_readline()
668 			strend = memchr(fr->mmapptr, fr->elsymb, sz);  in file_reader_readline()
671 				ret = bwscsbdup(fr->mmapptr, sz);  in file_reader_readline()
672 				fr->mmapptr = mmapend;  in file_reader_readline()
674 				ret = bwscsbdup(fr->mmapptr, strend -  in file_reader_readline()
675 				    fr->mmapptr);  in file_reader_readline()
676 				fr->mmapptr = strend + 1;  in file_reader_readline()
682 		len = getdelim(&fr->buffer, &fr->bsz, fr->elsymb, fr->file);  in file_reader_readline()
684 			if (!feof(fr->file))  in file_reader_readline()
688 		if (len > 0 && fr->buffer[len - 1] == fr->elsymb)  in file_reader_readline()
689 			len--;  in file_reader_readline()
690 		ret = bwscsbdup(fr->buffer, len);  in file_reader_readline()
703 	if (fr->mmapaddr)  in file_reader_clean()
704 		munmap(fr->mmapaddr, fr->mmapsize);  in file_reader_clean()
705 	if (fr->fd)  in file_reader_clean()
706 		close(fr->fd);  in file_reader_clean()
708 	free(fr->buffer);  in file_reader_clean()
709 	closefile(fr->file, fr->fname);  in file_reader_clean()
710 	free(fr->fname);  in file_reader_clean()
744 		if (list->memsize >= available_free_memory) {  in procfile()
769 		if (f1->fr == NULL) {  in file_header_cmp()
770 			return ((f2->fr == NULL) ? 0 : +1);  in file_header_cmp()
771 		} else if (f2->fr == NULL)  in file_header_cmp()
772 			return (-1);  in file_header_cmp()
776 			ret = list_coll(&(f1->si), &(f2->si));  in file_header_cmp()
778 				return ((f1->file_pos < f2->file_pos) ? -1 : +1);  in file_header_cmp()
795 		(*fh)->file_pos = file_pos;  in file_header_init()
796 		(*fh)->fr = file_reader_init(fn);  in file_header_init()
797 		if ((*fh)->fr == NULL) {  in file_header_init()
801 		line = file_reader_readline((*fh)->fr);  in file_header_init()
803 			file_reader_free((*fh)->fr);  in file_header_init()
804 			(*fh)->fr = NULL;  in file_header_init()
805 			(*fh)->si = NULL;  in file_header_init()
807 			(*fh)->si = sort_list_item_alloc();  in file_header_init()
808 			sort_list_item_set((*fh)->si, line);  in file_header_init()
821 		file_reader_free((*fh)->fr);  in file_header_close()
822 		(*fh)->fr = NULL;  in file_header_close()
823 		if ((*fh)->si) {  in file_header_close()
824 			sort_list_item_clean((*fh)->si);  in file_header_close()
825 			sort_free((*fh)->si);  in file_header_close()
826 			(*fh)->si = NULL;  in file_header_close()
859 		parent_index = (indx - 1) >> 1;  in file_header_heap_swim()
917 	file_header_heap_swim(fh, size - 1);  in file_header_list_push()
932 	if (fh && fh->fr && f_out && fh->si && fh->si->str) {  in file_header_print()
934 			if ((lp->str == NULL) || (str_list_coll(lp->str, &(fh->si)))) {  in file_header_print()
935 				bwsfwrite(fh->si->str, f_out, sort_opts_vals.zflag);  in file_header_print()
936 				if (lp->str)  in file_header_print()
937 					bwsfree(lp->str);  in file_header_print()
938 				lp->str = bwsdup(fh->si->str);  in file_header_print()
941 			bwsfwrite(fh->si->str, f_out, sort_opts_vals.zflag);  in file_header_print()
952 	if (fh && fh->fr) {  in file_header_read_next()
955 		tmp = file_reader_readline(fh->fr);  in file_header_read_next()
957 			file_reader_free(fh->fr);  in file_header_read_next()
958 			fh->fr = NULL;  in file_header_read_next()
959 			if (fh->si) {  in file_header_read_next()
960 				sort_list_item_clean(fh->si);  in file_header_read_next()
961 				sort_free(fh->si);  in file_header_read_next()
962 				fh->si = NULL;  in file_header_read_next()
965 			if (fh->si == NULL)  in file_header_read_next()
966 				fh->si = sort_list_item_alloc();  in file_header_read_next()
967 			sort_list_item_set(fh->si, tmp);  in file_header_read_next()
989 	while (fh[0]->fr) { /* unfinished files are always in front */  in file_headers_merge()
994 		/* re-arrange the list: */  in file_headers_merge()
1043 	if ((fl == NULL) || (size_t) (fl->count) < max_open_files)  in shrink_file_list()
1050 		while (indx < fl->count) {  in shrink_file_list()
1054 			num = fl->count - indx;  in shrink_file_list()
1058 				num = max_open_files - 1;  in shrink_file_list()
1059 			merge_files_array(num, fl->fns + indx, fnew);  in shrink_file_list()
1060 			if (fl->tmp) {  in shrink_file_list()
1064 					unlink(fl->fns[indx + i]);  in shrink_file_list()
1069 		fl->tmp = false; /* already taken care of */  in shrink_file_list()
1072 		fl->count = new_fl.count;  in shrink_file_list()
1073 		fl->fns = new_fl.fns;  in shrink_file_list()
1074 		fl->sz = new_fl.sz;  in shrink_file_list()
1075 		fl->tmp = new_fl.tmp;  in shrink_file_list()
1091 		merge_files_array(fl->count, fl->fns, fn_out);  in merge_files()
1128 	if (!(sm->Mflag) && !(sm->Rflag) && !(sm->Vflag) &&  in sort_list_to_file()
1129 	    !(sm->gflag) && !(sm->hflag) && !(sm->nflag)) {  in sort_list_to_file()
1163 		rxsort(list->list, list->count);  in sort_list_to_file()
1192  * Sort cycle thread (in multi-threaded mode)
1199 	g_sort_func(list->list, list->count, sizeof(struct sort_list_item *),  in mt_sort_thread()
1208  * Compare sub-lists. Empty sub-lists always go to the end of the list.
1217 		if (l1->count == 0) {  in sub_list_cmp()
1218 			return ((l2->count == 0) ? 0 : +1);  in sub_list_cmp()
1219 		} else if (l2->count == 0) {  in sub_list_cmp()
1220 			return (-1);  in sub_list_cmp()
1224 			ret = list_coll(&(l1->list[0]), &(l2->list[0]));  in sub_list_cmp()
1226 				return ((l1->sub_list_pos < l2->sub_list_pos) ?  in sub_list_cmp()
1227 				    -1 : +1);  in sub_list_cmp()
1259 		parent_index = (indx - 1) >> 1;  in sub_list_swim()
1307 	sub_list_swim(sl, size - 1);  in sub_list_push()
1323 	if (sl && sl->count && f_out && sl->list[0]->str) {  in sub_list_header_print()
1325 			if ((lp->item == NULL) || (list_coll(&(lp->item),  in sub_list_header_print()
1326 			    &(sl->list[0])))) {  in sub_list_header_print()
1327 				bwsfwrite(sl->list[0]->str, f_out,  in sub_list_header_print()
1329 				lp->item = sl->list[0];  in sub_list_header_print()
1332 			bwsfwrite(sl->list[0]->str, f_out,  in sub_list_header_print()
1344 	if (sl && sl->count) {  in sub_list_next()
1345 		sl->list += 1;  in sub_list_next()
1346 		sl->count -= 1;  in sub_list_next()
1351  * Merge sub-lists to a file
1365 	while (sl[0]->count) { /* unfinished lists are always in front */  in merge_sub_lists()
1370 		/* re-arrange the list: */  in merge_sub_lists()
1376  * Merge sub-lists to a file
1379 merge_list_parts(struct sort_list **parts, size_t n, const char *fn)  in merge_list_parts()  argument
1385 	merge_sub_lists(parts, n, f_out);  in merge_list_parts()
1392  * Multi-threaded sort algorithm "driver"
1400 	if (nthreads < 2 || list->count < MT_SORT_THRESHOLD) {  in mt_sort()
1405 		sort_func(list->list, list->count,  in mt_sort()
1412 		/* multi-threaded sort */  in mt_sort()
1413 		struct sort_list **parts;  in mt_sort()  local
1416 		/* array of sub-lists */  in mt_sort()
1417 		parts = sort_malloc(sizeof(struct sort_list*) * nthreads);  in mt_sort()
1419 		avgsize = list->count / nthreads;  in mt_sort()
1428 			parts[i] = sort_malloc(sizeof(struct sort_list));  in mt_sort()
1429 			parts[i]->list = list->list + cstart;  in mt_sort()
1430 			parts[i]->memsize = 0;  in mt_sort()
1431 			parts[i]->sub_list_pos = i;  in mt_sort()
1433 			sz = (i == nthreads - 1) ? list->count - cstart :  in mt_sort()
1436 			parts[i]->count = sz;  in mt_sort()
1438 			parts[i]->size = parts[i]->count;  in mt_sort()
1456 				    mt_sort_thread, parts[i]);  in mt_sort()
1474 		/* destroy the semaphore - we do not need it anymore */  in mt_sort()
1477 		/* merge sorted sub-lists to the file */  in mt_sort()
1478 		merge_list_parts(parts, nthreads, fn);  in mt_sort()
1480 		/* free sub-lists data */  in mt_sort()
1482 			sort_free(parts[i]);  in mt_sort()
1484 		sort_free(parts);  in mt_sort()