Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	usr.bin/sort/radixsort.c	Lines:	191	194	98.5 %
Date:	2017-11-13	Branches:	72	80	90.0 %


/*	$OpenBSD: radixsort.c,v 1.5 2015/04/02 21:00:08 tobias Exp $	*/

/*-
 * Copyright (C) 2012 Oleg Moskalenko <mom040267@gmail.com>
 * Copyright (C) 2012 Gabor Kovesdan <gabor@FreeBSD.org>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <errno.h>
#include <err.h>
#include <langinfo.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <wchar.h>
#include <wctype.h>
#include <unistd.h>

#include "coll.h"
#include "radixsort.h"

#define DEFAULT_SORT_FUNC_RADIXSORT mergesort

#define TINY_NODE(sl) ((sl)->tosort_num < 65)
#define SMALL_NODE(sl) ((sl)->tosort_num < 5)

/* are we sorting in reverse order ? */
static bool reverse_sort;

/* sort sub-levels array size */
static const size_t slsz = 256 * sizeof(struct sort_level *);

/* one sort level structure */
struct sort_level {
	struct sort_level	**sublevels;
	struct sort_list_item	**leaves;
	struct sort_list_item	**sorted;
	struct sort_list_item	**tosort;
	size_t			  leaves_num;
	size_t			  leaves_sz;
	size_t			  level;
	size_t			  real_sln;
	size_t			  start_position;
	size_t			  sln;
	size_t			  tosort_num;
	size_t			  tosort_sz;
};

/* stack of sort levels ready to be sorted */
struct level_stack {
	struct level_stack	 *next;
	struct sort_level	 *sl;
};

static struct level_stack *g_ls;

/*
 * Push sort level to the stack
 */
static inline void
push_ls(struct sort_level *sl)
{
	struct level_stack *new_ls;

	new_ls = sort_malloc(sizeof(struct level_stack));
	new_ls->sl = sl;

	new_ls->next = g_ls;
	g_ls = new_ls;
}

/*
 * Pop sort level from the stack (single-threaded style)
 */
static inline struct sort_level *
pop_ls_st(void)
{
	struct sort_level *sl;

	if (g_ls) {
		struct level_stack *saved_ls;

		sl = g_ls->sl;
		saved_ls = g_ls;
		g_ls = g_ls->next;
		sort_free(saved_ls);
	} else
		sl = NULL;

	return sl;
}

static void
add_to_sublevel(struct sort_level *sl, struct sort_list_item *item, size_t indx)
{
	struct sort_level *ssl;

	ssl = sl->sublevels[indx];

	if (ssl == NULL) {
		ssl = sort_calloc(1, sizeof(struct sort_level));
		ssl->level = sl->level + 1;
		sl->sublevels[indx] = ssl;

		++(sl->real_sln);
	}

	if (++(ssl->tosort_num) > ssl->tosort_sz) {
		ssl->tosort_sz = ssl->tosort_num + 128;
		ssl->tosort = sort_reallocarray(ssl->tosort, ssl->tosort_sz,
		    sizeof(struct sort_list_item *));
	}

	ssl->tosort[ssl->tosort_num - 1] = item;
}

static inline void
add_leaf(struct sort_level *sl, struct sort_list_item *item)
{
	if (++(sl->leaves_num) > sl->leaves_sz) {
		sl->leaves_sz = sl->leaves_num + 128;
		sl->leaves = sort_reallocarray(sl->leaves, sl->leaves_sz,
		    sizeof(struct sort_list_item *));
	}
	sl->leaves[sl->leaves_num - 1] = item;
}

static inline int
get_wc_index(struct sort_list_item *sli, size_t level)
{
	const struct bwstring *bws;

	bws = sli->ka.key[0].k;

	if ((BWSLEN(bws) > level))
		return (unsigned char)BWS_GET(bws, level);
	return -1;
}

static void
place_item(struct sort_level *sl, size_t item)
{
	struct sort_list_item *sli;
	int c;

	sli = sl->tosort[item];
	c = get_wc_index(sli, sl->level);

	if (c == -1)
		add_leaf(sl, sli);
	else
		add_to_sublevel(sl, sli, c);
}

static void
free_sort_level(struct sort_level *sl)
{
	if (sl) {
		sort_free(sl->leaves);

		if (sl->level > 0)
			sort_free(sl->tosort);

		if (sl->sublevels) {
			struct sort_level *slc;
			size_t i, sln;

			sln = sl->sln;

			for (i = 0; i < sln; ++i) {
				slc = sl->sublevels[i];
				free_sort_level(slc);
			}

			sort_free(sl->sublevels);
		}

		sort_free(sl);
	}
}

static void
run_sort_level_next(struct sort_level *sl)
{
	struct sort_level *slc;
	size_t i, sln, tosort_num;

	sort_free(sl->sublevels);
	sl->sublevels = NULL;

	switch (sl->tosort_num) {
	case 0:
		goto end;
	case 1:
		sl->sorted[sl->start_position] = sl->tosort[0];
		goto end;
	case 2:
		if (list_coll_offset(&(sl->tosort[0]), &(sl->tosort[1]),
		    sl->level) > 0) {
			sl->sorted[sl->start_position++] = sl->tosort[1];
			sl->sorted[sl->start_position] = sl->tosort[0];
		} else {
			sl->sorted[sl->start_position++] = sl->tosort[0];
			sl->sorted[sl->start_position] = sl->tosort[1];
		}

		goto end;
	default:
		if (TINY_NODE(sl) || (sl->level > 15)) {
			listcoll_t func;

			func = get_list_call_func(sl->level);

			sl->leaves = sl->tosort;
			sl->leaves_num = sl->tosort_num;
			sl->leaves_sz = sl->leaves_num;
			sl->leaves = sort_reallocarray(sl->leaves,
			    sl->leaves_sz, sizeof(struct sort_list_item *));
			sl->tosort = NULL;
			sl->tosort_num = 0;
			sl->tosort_sz = 0;
			sl->sln = 0;
			sl->real_sln = 0;
			if (sort_opts_vals.sflag) {
				if (mergesort(sl->leaves, sl->leaves_num,
				    sizeof(struct sort_list_item *),
				    (int(*)(const void *, const void *)) func) == -1)
					/* NOTREACHED */
					err(2, "Radix sort error 3");
			} else
				DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
				    sizeof(struct sort_list_item *),
				    (int(*)(const void *, const void *)) func);

			memcpy(sl->sorted + sl->start_position,
			    sl->leaves, sl->leaves_num *
			    sizeof(struct sort_list_item *));

			goto end;
		} else {
			sl->tosort_sz = sl->tosort_num;
			sl->tosort = sort_reallocarray(sl->tosort,
			    sl->tosort_sz, sizeof(struct sort_list_item *));
		}
	}

	sl->sln = 256;
	sl->sublevels = sort_calloc(1, slsz);
	sl->real_sln = 0;

	tosort_num = sl->tosort_num;
	for (i = 0; i < tosort_num; ++i)
		place_item(sl, i);

	sort_free(sl->tosort);
	sl->tosort = NULL;
	sl->tosort_num = 0;
	sl->tosort_sz = 0;

	if (sl->leaves_num > 1) {
		if (keys_num > 1) {
			if (sort_opts_vals.sflag) {
				mergesort(sl->leaves, sl->leaves_num,
				    sizeof(struct sort_list_item *), list_coll);
			} else {
				DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
				    sizeof(struct sort_list_item *), list_coll);
			}
		} else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) {
			DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
			    sizeof(struct sort_list_item *), list_coll);
		}
	}

	sl->leaves_sz = sl->leaves_num;
	sl->leaves = sort_reallocarray(sl->leaves, sl->leaves_sz,
	    sizeof(struct sort_list_item *));

	if (!reverse_sort) {
		memcpy(sl->sorted + sl->start_position, sl->leaves,
		    sl->leaves_num * sizeof(struct sort_list_item *));
		sl->start_position += sl->leaves_num;

		sort_free(sl->leaves);
		sl->leaves = NULL;
		sl->leaves_num = 0;
		sl->leaves_sz = 0;

		sln = sl->sln;

		for (i = 0; i < sln; ++i) {
			slc = sl->sublevels[i];

			if (slc) {
				slc->sorted = sl->sorted;
				slc->start_position = sl->start_position;
				sl->start_position += slc->tosort_num;
				if (SMALL_NODE(slc))
					run_sort_level_next(slc);
				else
					push_ls(slc);
				sl->sublevels[i] = NULL;
			}
		}

	} else {
		size_t n;

		sln = sl->sln;

		for (i = 0; i < sln; ++i) {
			n = sln - i - 1;
			slc = sl->sublevels[n];

			if (slc) {
				slc->sorted = sl->sorted;
				slc->start_position = sl->start_position;
				sl->start_position += slc->tosort_num;
				if (SMALL_NODE(slc))
					run_sort_level_next(slc);
				else
					push_ls(slc);
				sl->sublevels[n] = NULL;
			}
		}

		memcpy(sl->sorted + sl->start_position, sl->leaves,
		    sl->leaves_num * sizeof(struct sort_list_item *));
	}

end:
	free_sort_level(sl);
}

/*
 * Single-threaded sort cycle
 */
static void
run_sort_cycle_st(void)
{
	struct sort_level *slc;

	for (;;) {
		slc = pop_ls_st();
		if (slc == NULL) {
			break;
		}
		run_sort_level_next(slc);
	}
}

static void
run_top_sort_level(struct sort_level *sl)
{
	struct sort_level *slc;
	size_t i;

	reverse_sort = sort_opts_vals.kflag ? keys[0].sm.rflag :
	    default_sort_mods->rflag;

	sl->start_position = 0;
	sl->sln = 256;
	sl->sublevels = sort_calloc(1, slsz);

	for (i = 0; i < sl->tosort_num; ++i)
		place_item(sl, i);

	if (sl->leaves_num > 1) {
		if (keys_num > 1) {
			if (sort_opts_vals.sflag) {
				mergesort(sl->leaves, sl->leaves_num,
				    sizeof(struct sort_list_item *), list_coll);
			} else {
				DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
				    sizeof(struct sort_list_item *), list_coll);
			}
		} else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) {
			DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
			    sizeof(struct sort_list_item *), list_coll);
		}
	}

	if (!reverse_sort) {
		size_t i;

		memcpy(sl->tosort + sl->start_position, sl->leaves,
		    sl->leaves_num * sizeof(struct sort_list_item *));
		sl->start_position += sl->leaves_num;

		for (i = 0; i < sl->sln; ++i) {
			slc = sl->sublevels[i];

			if (slc) {
				slc->sorted = sl->tosort;
				slc->start_position = sl->start_position;
				sl->start_position += slc->tosort_num;
				push_ls(slc);
				sl->sublevels[i] = NULL;
			}
		}

	} else {
		size_t i, n;

		for (i = 0; i < sl->sln; ++i) {

			n = sl->sln - i - 1;
			slc = sl->sublevels[n];

			if (slc) {
				slc->sorted = sl->tosort;
				slc->start_position = sl->start_position;
				sl->start_position += slc->tosort_num;
				push_ls(slc);
				sl->sublevels[n] = NULL;
			}
		}

		memcpy(sl->tosort + sl->start_position, sl->leaves,
		    sl->leaves_num * sizeof(struct sort_list_item *));
	}
	run_sort_cycle_st();
}

void
rxsort(struct sort_list_item **base, size_t nmemb)
{
	struct sort_level *sl;

	sl = sort_calloc(1, sizeof(struct sort_level));
	sl->tosort = base;
	sl->tosort_num = nmemb;
	sl->tosort_sz = nmemb;

	run_top_sort_level(sl);

	free_sort_level(sl);
}


Generated by: GCOVR (Version 3.3)

Line	Branch	Exec	Source
1			/* $OpenBSD: radixsort.c,v 1.5 2015/04/02 21:00:08 tobias Exp $ */
2
3			/*-
4			* Copyright (C) 2012 Oleg Moskalenko <mom040267@gmail.com>
5			* Copyright (C) 2012 Gabor Kovesdan <gabor@FreeBSD.org>
6			* All rights reserved.
7			*
8			* Redistribution and use in source and binary forms, with or without
9			* modification, are permitted provided that the following conditions
10			* are met:
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.
16			*
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
27			* SUCH DAMAGE.
28			*/
29
30			#include <errno.h>
31			#include <err.h>
32			#include <langinfo.h>
33			#include <math.h>
34			#include <stdlib.h>
35			#include <string.h>
36			#include <wchar.h>
37			#include <wctype.h>
38			#include <unistd.h>
39
40			#include "coll.h"
41			#include "radixsort.h"
42
43			#define DEFAULT_SORT_FUNC_RADIXSORT mergesort
44
45			#define TINY_NODE(sl) ((sl)->tosort_num < 65)
46			#define SMALL_NODE(sl) ((sl)->tosort_num < 5)
47
48			/* are we sorting in reverse order ? */
49			static bool reverse_sort;
50
51			/* sort sub-levels array size */
52			static const size_t slsz = 256 * sizeof(struct sort_level *);
53
54			/* one sort level structure */
55			struct sort_level {
56			struct sort_level **sublevels;
57			struct sort_list_item **leaves;
58			struct sort_list_item **sorted;
59			struct sort_list_item **tosort;
60			size_t leaves_num;
61			size_t leaves_sz;
62			size_t level;
63			size_t real_sln;
64			size_t start_position;
65			size_t sln;
66			size_t tosort_num;
67			size_t tosort_sz;
68			};
69
70			/* stack of sort levels ready to be sorted */
71			struct level_stack {
72			struct level_stack *next;
73			struct sort_level *sl;
74			};
75
76			static struct level_stack *g_ls;
77
78			/*
79			* Push sort level to the stack
80			*/
81			static inline void
82			push_ls(struct sort_level *sl)
83			{
84			struct level_stack *new_ls;
85
86		244064	new_ls = sort_malloc(sizeof(struct level_stack));
87		122032	new_ls->sl = sl;
88
89		122032	new_ls->next = g_ls;
90		122032	g_ls = new_ls;
91		122032	}
92
93			/*
94			* Pop sort level from the stack (single-threaded style)
95			*/
96			static inline struct sort_level *
97			pop_ls_st(void)
98			{
99			struct sort_level *sl;
100
101	✓✓	245370	if (g_ls) {
102			struct level_stack *saved_ls;
103
104		122032	sl = g_ls->sl;
105			saved_ls = g_ls;
106		122032	g_ls = g_ls->next;
107		122032	sort_free(saved_ls);
108		122032	} else
109			sl = NULL;
110
111		122685	return sl;
112			}
113
114			static void
115			add_to_sublevel(struct sort_level sl, struct sort_list_item item, size_t indx)
116			{
117			struct sort_level *ssl;
118
119		25592112	ssl = sl->sublevels[indx];
120
121	✓✓	12796056	if (ssl == NULL) {
122		164895	ssl = sort_calloc(1, sizeof(struct sort_level));
123		164895	ssl->level = sl->level + 1;
124		164895	sl->sublevels[indx] = ssl;
125
126		164895	++(sl->real_sln);
127		164895	}
128
129	✓✓	12796056	if (++(ssl->tosort_num) > ssl->tosort_sz) {
130		239933	ssl->tosort_sz = ssl->tosort_num + 128;
131		239933	ssl->tosort = sort_reallocarray(ssl->tosort, ssl->tosort_sz,
132			sizeof(struct sort_list_item *));
133		239933	}
134
135		12796056	ssl->tosort[ssl->tosort_num - 1] = item;
136		12796056	}
137
138			static inline void
139			add_leaf(struct sort_level sl, struct sort_list_item item)
140			{
141	✓✓	2347170	if (++(sl->leaves_num) > sl->leaves_sz) {
142		12965	sl->leaves_sz = sl->leaves_num + 128;
143		12965	sl->leaves = sort_reallocarray(sl->leaves, sl->leaves_sz,
144			sizeof(struct sort_list_item *));
145		12965	}
146		1173585	sl->leaves[sl->leaves_num - 1] = item;
147		1173585	}
148
149			static inline int
150			get_wc_index(struct sort_list_item *sli, size_t level)
151			{
152			const struct bwstring *bws;
153
154		27939282	bws = sli->ka.key[0].k;
155
156	✓✓	13969641	if ((BWSLEN(bws) > level))
157	✓✗	38388168	return (unsigned char)BWS_GET(bws, level);
158		1173585	return -1;
159		13969641	}
160
161			static void
162			place_item(struct sort_level *sl, size_t item)
163			{
164			struct sort_list_item *sli;
165			int c;
166
167		27939282	sli = sl->tosort[item];
168		13969641	c = get_wc_index(sli, sl->level);
169
170	✓✓	13969641	if (c == -1)
171		1173585	add_leaf(sl, sli);
172			else
173		12796056	add_to_sublevel(sl, sli, c);
174		13969641	}
175
176			static void
177			free_sort_level(struct sort_level *sl)
178			{
179	✓✓	9861464	if (sl) {
180		165548	sort_free(sl->leaves);
181
182	✓✓	165548	if (sl->level > 0)
183		164895	sort_free(sl->tosort);
184
185	✓✓	165548	if (sl->sublevels) {
186			struct sort_level *slc;
187			size_t i, sln;
188
189		18614	sln = sl->sln;
190
191	✓✓	9567596	for (i = 0; i < sln; ++i) {
192		4765184	slc = sl->sublevels[i];
193		4765184	free_sort_level(slc);
194			}
195
196		18614	sort_free(sl->sublevels);
197		18614	}
198
199		165548	sort_free(sl);
200		165548	}
201		4930732	}
202
203			static void
204			run_sort_level_next(struct sort_level *sl)
205			{
206			struct sort_level *slc;
207			size_t i, sln, tosort_num;
208
209		494685	sort_free(sl->sublevels);
210		329790	sl->sublevels = NULL;
211
212	✓✓✓✓	329790	switch (sl->tosort_num) {
213			case 0:
214			goto end;
215			case 1:
216		19085	sl->sorted[sl->start_position] = sl->tosort[0];
217		19085	goto end;
218			case 2:
219	✓✓	31575	if (list_coll_offset(&(sl->tosort[0]), &(sl->tosort[1]),
220		21050	sl->level) > 0) {
221		312	sl->sorted[sl->start_position++] = sl->tosort[1];
222		312	sl->sorted[sl->start_position] = sl->tosort[0];
223		312	} else {
224		10213	sl->sorted[sl->start_position++] = sl->tosort[0];
225		10213	sl->sorted[sl->start_position] = sl->tosort[1];
226			}
227
228		10525	goto end;
229			default:
230	✓✓✓✓	153350	if (TINY_NODE(sl) \|\| (sl->level > 15)) {
231			listcoll_t func;
232
233		117324	func = get_list_call_func(sl->level);
234
235		117324	sl->leaves = sl->tosort;
236		117324	sl->leaves_num = sl->tosort_num;
237		117324	sl->leaves_sz = sl->leaves_num;
238		117324	sl->leaves = sort_reallocarray(sl->leaves,
239			sl->leaves_sz, sizeof(struct sort_list_item *));
240		117324	sl->tosort = NULL;
241		117324	sl->tosort_num = 0;
242		117324	sl->tosort_sz = 0;
243		117324	sl->sln = 0;
244		117324	sl->real_sln = 0;
245	✗✓	234648	if (sort_opts_vals.sflag) {
246		117324	if (mergesort(sl->leaves, sl->leaves_num,
247			sizeof(struct sort_list_item *),
248		117324	(int()(const void , const void *)) func) == -1)
249			/* NOTREACHED */
250			err(2, "Radix sort error 3");
251			} else
252			DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
253			sizeof(struct sort_list_item *),
254			(int()(const void , const void *)) func);
255
256		351972	memcpy(sl->sorted + sl->start_position,
257		234648	sl->leaves, sl->leaves_num *
258			sizeof(struct sort_list_item *));
259
260			goto end;
261			} else {
262		17961	sl->tosort_sz = sl->tosort_num;
263		17961	sl->tosort = sort_reallocarray(sl->tosort,
264			sl->tosort_sz, sizeof(struct sort_list_item *));
265			}
266			}
267
268		17961	sl->sln = 256;
269		17961	sl->sublevels = sort_calloc(1, slsz);
270		17961	sl->real_sln = 0;
271
272		17961	tosort_num = sl->tosort_num;
273	✓✓	22109134	for (i = 0; i < tosort_num; ++i)
274		11036606	place_item(sl, i);
275
276		17961	sort_free(sl->tosort);
277		17961	sl->tosort = NULL;
278		17961	sl->tosort_num = 0;
279		17961	sl->tosort_sz = 0;
280
281	✓✓	17961	if (sl->leaves_num > 1) {
282	✗✓	655	if (keys_num > 1) {
283			if (sort_opts_vals.sflag) {
284			mergesort(sl->leaves, sl->leaves_num,
285			sizeof(struct sort_list_item *), list_coll);
286			} else {
287			DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
288			sizeof(struct sort_list_item *), list_coll);
289			}
290	✓✓✓✓	1197	} else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) {
291		524	DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
292			sizeof(struct sort_list_item *), list_coll);
293		524	}
294			}
295
296		17961	sl->leaves_sz = sl->leaves_num;
297		17961	sl->leaves = sort_reallocarray(sl->leaves, sl->leaves_sz,
298			sizeof(struct sort_list_item *));
299
300	✓✓	17961	if (!reverse_sort) {
301		33234	memcpy(sl->sorted + sl->start_position, sl->leaves,
302		16617	sl->leaves_num * sizeof(struct sort_list_item *));
303		16617	sl->start_position += sl->leaves_num;
304
305		16617	sort_free(sl->leaves);
306		16617	sl->leaves = NULL;
307		16617	sl->leaves_num = 0;
308		16617	sl->leaves_sz = 0;
309
310		16617	sln = sl->sln;
311
312	✓✓	8541138	for (i = 0; i < sln; ++i) {
313		4253952	slc = sl->sublevels[i];
314
315	✓✓	4253952	if (slc) {
316		150550	slc->sorted = sl->sorted;
317		150550	slc->start_position = sl->start_position;
318		150550	sl->start_position += slc->tosort_num;
319	✓✓	150550	if (SMALL_NODE(slc))
320		42860	run_sort_level_next(slc);
321			else
322		107690	push_ls(slc);
323		150550	sl->sublevels[i] = NULL;
324		150550	}
325			}
326
327			} else {
328			size_t n;
329
330		1344	sln = sl->sln;
331
332	✓✓	690816	for (i = 0; i < sln; ++i) {
333		344064	n = sln - i - 1;
334		344064	slc = sl->sublevels[n];
335
336	✓✓	344064	if (slc) {
337		13332	slc->sorted = sl->sorted;
338		13332	slc->start_position = sl->start_position;
339		13332	sl->start_position += slc->tosort_num;
340	✓✓	13332	if (SMALL_NODE(slc))
341		3	run_sort_level_next(slc);
342			else
343		13329	push_ls(slc);
344		13332	sl->sublevels[n] = NULL;
345		13332	}
346			}
347
348		2688	memcpy(sl->sorted + sl->start_position, sl->leaves,
349		1344	sl->leaves_num * sizeof(struct sort_list_item *));
350			}
351
352			end:
353		164895	free_sort_level(sl);
354		164895	}
355
356			/*
357			* Single-threaded sort cycle
358			*/
359			static void
360			run_sort_cycle_st(void)
361			{
362			struct sort_level *slc;
363
364		123338	for (;;) {
365		122685	slc = pop_ls_st();
366	✓✓	122685	if (slc == NULL) {
367			break;
368			}
369		122032	run_sort_level_next(slc);
370			}
371		653	}
372
373			static void
374			run_top_sort_level(struct sort_level *sl)
375			{
376			struct sort_level *slc;
377			size_t i;
378
379		1959	reverse_sort = sort_opts_vals.kflag ? keys[0].sm.rflag :
380		653	default_sort_mods->rflag;
381
382		653	sl->start_position = 0;
383		653	sl->sln = 256;
384		653	sl->sublevels = sort_calloc(1, slsz);
385
386	✓✓	5867376	for (i = 0; i < sl->tosort_num; ++i)
387		2933035	place_item(sl, i);
388
389	✓✓	653	if (sl->leaves_num > 1) {
390	✓✗	16	if (keys_num > 1) {
391			if (sort_opts_vals.sflag) {
392		16	mergesort(sl->leaves, sl->leaves_num,
393			sizeof(struct sort_list_item *), list_coll);
394			} else {
395			DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
396			sizeof(struct sort_list_item *), list_coll);
397			}
398	✗✗✗✗	16	} else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) {
399			DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
400			sizeof(struct sort_list_item *), list_coll);
401			}
402			}
403
404	✓✓	653	if (!reverse_sort) {
405			size_t i;
406
407		1218	memcpy(sl->tosort + sl->start_position, sl->leaves,
408		609	sl->leaves_num * sizeof(struct sort_list_item *));
409		609	sl->start_position += sl->leaves_num;
410
411	✓✓	313026	for (i = 0; i < sl->sln; ++i) {
412		155904	slc = sl->sublevels[i];
413
414	✓✓	155904	if (slc) {
415		934	slc->sorted = sl->tosort;
416		934	slc->start_position = sl->start_position;
417		934	sl->start_position += slc->tosort_num;
418		934	push_ls(slc);
419		934	sl->sublevels[i] = NULL;
420		934	}
421			}
422
423		609	} else {
424			size_t i, n;
425
426	✓✓	22616	for (i = 0; i < sl->sln; ++i) {
427
428		11264	n = sl->sln - i - 1;
429		11264	slc = sl->sublevels[n];
430
431	✓✓	11264	if (slc) {
432		79	slc->sorted = sl->tosort;
433		79	slc->start_position = sl->start_position;
434		79	sl->start_position += slc->tosort_num;
435		79	push_ls(slc);
436		79	sl->sublevels[n] = NULL;
437		79	}
438			}
439
440		88	memcpy(sl->tosort + sl->start_position, sl->leaves,
441		44	sl->leaves_num * sizeof(struct sort_list_item *));
442			}
443		653	run_sort_cycle_st();
444		653	}
445
446			void
447			rxsort(struct sort_list_item **base, size_t nmemb)
448			{
449			struct sort_level *sl;
450
451		1306	sl = sort_calloc(1, sizeof(struct sort_level));
452		653	sl->tosort = base;
453		653	sl->tosort_num = nmemb;
454		653	sl->tosort_sz = nmemb;
455
456		653	run_top_sort_level(sl);
457
458		653	free_sort_level(sl);
459		653	}