GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.bin/sort/radixsort.c Lines: 190 194 97.9 %
Date: 2017-11-07 Branches: 71 80 88.8 %

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
256218
	new_ls = sort_malloc(sizeof(struct level_stack));
87
128109
	new_ls->sl = sl;
88
89
128109
	new_ls->next = g_ls;
90
128109
	g_ls = new_ls;
91
128109
}
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
257716
	if (g_ls) {
102
		struct level_stack *saved_ls;
103
104
128109
		sl = g_ls->sl;
105
		saved_ls = g_ls;
106
128109
		g_ls = g_ls->next;
107
128109
		sort_free(saved_ls);
108
128109
	} else
109
		sl = NULL;
110
111
128858
	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
27317954
	ssl = sl->sublevels[indx];
120
121
13658977
	if (ssl == NULL) {
122
174072
		ssl = sort_calloc(1, sizeof(struct sort_level));
123
174072
		ssl->level = sl->level + 1;
124
174072
		sl->sublevels[indx] = ssl;
125
126
174072
		++(sl->real_sln);
127
174072
	}
128
129
13658977
	if (++(ssl->tosort_num) > ssl->tosort_sz) {
130
254160
		ssl->tosort_sz = ssl->tosort_num + 128;
131
254160
		ssl->tosort = sort_reallocarray(ssl->tosort, ssl->tosort_sz,
132
		    sizeof(struct sort_list_item *));
133
254160
	}
134
135
13658977
	ssl->tosort[ssl->tosort_num - 1] = item;
136
13658977
}
137
138
static inline void
139
add_leaf(struct sort_level *sl, struct sort_list_item *item)
140
{
141
2368416
	if (++(sl->leaves_num) > sl->leaves_sz) {
142
13047
		sl->leaves_sz = sl->leaves_num + 128;
143
13047
		sl->leaves = sort_reallocarray(sl->leaves, sl->leaves_sz,
144
		    sizeof(struct sort_list_item *));
145
13047
	}
146
1184208
	sl->leaves[sl->leaves_num - 1] = item;
147
1184208
}
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
29686370
	bws = sli->ka.key[0].k;
155
156
14843185
	if ((BWSLEN(bws) > level))
157
40976931
		return (unsigned char)BWS_GET(bws, level);
158
1184208
	return -1;
159
14843185
}
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
29686370
	sli = sl->tosort[item];
168
14843185
	c = get_wc_index(sli, sl->level);
169
170
14843185
	if (c == -1)
171
1184208
		add_leaf(sl, sli);
172
	else
173
13658977
		add_to_sublevel(sl, sli, c);
174
14843185
}
175
176
static void
177
free_sort_level(struct sort_level *sl)
178
{
179
10947530
	if (sl) {
180
174821
		sort_free(sl->leaves);
181
182
174821
		if (sl->level > 0)
183
174072
			sort_free(sl->tosort);
184
185
174821
		if (sl->sublevels) {
186
			struct sort_level *slc;
187
			size_t i, sln;
188
189
20699
			sln = sl->sln;
190
191
10639286
			for (i = 0; i < sln; ++i) {
192
5298944
				slc = sl->sublevels[i];
193
5298944
				free_sort_level(slc);
194
			}
195
196
20699
			sort_free(sl->sublevels);
197
20699
		}
198
199
174821
		sort_free(sl);
200
174821
	}
201
5473765
}
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
522216
	sort_free(sl->sublevels);
210
348144
	sl->sublevels = NULL;
211
212

348144
	switch (sl->tosort_num) {
213
	case 0:
214
		goto end;
215
	case 1:
216
20898
		sl->sorted[sl->start_position] = sl->tosort[0];
217
20898
		goto end;
218
	case 2:
219
33543
		if (list_coll_offset(&(sl->tosort[0]), &(sl->tosort[1]),
220
22362
		    sl->level) > 0) {
221
456
			sl->sorted[sl->start_position++] = sl->tosort[1];
222
456
			sl->sorted[sl->start_position] = sl->tosort[0];
223
456
		} else {
224
10725
			sl->sorted[sl->start_position++] = sl->tosort[0];
225
10725
			sl->sorted[sl->start_position] = sl->tosort[1];
226
		}
227
228
11181
		goto end;
229
	default:
230

162094
		if (TINY_NODE(sl) || (sl->level > 15)) {
231
			listcoll_t func;
232
233
122043
			func = get_list_call_func(sl->level);
234
235
122043
			sl->leaves = sl->tosort;
236
122043
			sl->leaves_num = sl->tosort_num;
237
122043
			sl->leaves_sz = sl->leaves_num;
238
122043
			sl->leaves = sort_reallocarray(sl->leaves,
239
			    sl->leaves_sz, sizeof(struct sort_list_item *));
240
122043
			sl->tosort = NULL;
241
122043
			sl->tosort_num = 0;
242
122043
			sl->tosort_sz = 0;
243
122043
			sl->sln = 0;
244
122043
			sl->real_sln = 0;
245
244086
			if (sort_opts_vals.sflag) {
246
122043
				if (mergesort(sl->leaves, sl->leaves_num,
247
				    sizeof(struct sort_list_item *),
248
122043
				    (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
366129
			memcpy(sl->sorted + sl->start_position,
257
244086
			    sl->leaves, sl->leaves_num *
258
			    sizeof(struct sort_list_item *));
259
260
			goto end;
261
		} else {
262
19950
			sl->tosort_sz = sl->tosort_num;
263
19950
			sl->tosort = sort_reallocarray(sl->tosort,
264
			    sl->tosort_sz, sizeof(struct sort_list_item *));
265
		}
266
	}
267
268
19950
	sl->sln = 256;
269
19950
	sl->sublevels = sort_calloc(1, slsz);
270
19950
	sl->real_sln = 0;
271
272
19950
	tosort_num = sl->tosort_num;
273
23657836
	for (i = 0; i < tosort_num; ++i)
274
11808968
		place_item(sl, i);
275
276
19950
	sort_free(sl->tosort);
277
19950
	sl->tosort = NULL;
278
19950
	sl->tosort_num = 0;
279
19950
	sl->tosort_sz = 0;
280
281
19950
	if (sl->leaves_num > 1) {
282
705
		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

1297
		} else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) {
291
573
			DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
292
			    sizeof(struct sort_list_item *), list_coll);
293
573
		}
294
	}
295
296
19950
	sl->leaves_sz = sl->leaves_num;
297
19950
	sl->leaves = sort_reallocarray(sl->leaves, sl->leaves_sz,
298
	    sizeof(struct sort_list_item *));
299
300
19950
	if (!reverse_sort) {
301
37212
		memcpy(sl->sorted + sl->start_position, sl->leaves,
302
18606
		    sl->leaves_num * sizeof(struct sort_list_item *));
303
18606
		sl->start_position += sl->leaves_num;
304
305
18606
		sort_free(sl->leaves);
306
18606
		sl->leaves = NULL;
307
18606
		sl->leaves_num = 0;
308
18606
		sl->leaves_sz = 0;
309
310
18606
		sln = sl->sln;
311
312
9563484
		for (i = 0; i < sln; ++i) {
313
4763136
			slc = sl->sublevels[i];
314
315
4763136
			if (slc) {
316
159278
				slc->sorted = sl->sorted;
317
159278
				slc->start_position = sl->start_position;
318
159278
				sl->start_position += slc->tosort_num;
319
159278
				if (SMALL_NODE(slc))
320
45963
					run_sort_level_next(slc);
321
				else
322
113315
					push_ls(slc);
323
159278
				sl->sublevels[i] = NULL;
324
159278
			}
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
					run_sort_level_next(slc);
342
				else
343
13332
					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
174072
	free_sort_level(sl);
354
174072
}
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
129607
	for (;;) {
365
128858
		slc = pop_ls_st();
366
128858
		if (slc == NULL) {
367
			break;
368
		}
369
128109
		run_sort_level_next(slc);
370
	}
371
749
}
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
2247
	reverse_sort = sort_opts_vals.kflag ? keys[0].sm.rflag :
380
749
	    default_sort_mods->rflag;
381
382
749
	sl->start_position = 0;
383
749
	sl->sln = 256;
384
749
	sl->sublevels = sort_calloc(1, slsz);
385
386
6069932
	for (i = 0; i < sl->tosort_num; ++i)
387
3034217
		place_item(sl, i);
388
389
749
	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
749
	if (!reverse_sort) {
405
		size_t i;
406
407
1410
		memcpy(sl->tosort + sl->start_position, sl->leaves,
408
705
		    sl->leaves_num * sizeof(struct sort_list_item *));
409
705
		sl->start_position += sl->leaves_num;
410
411
362370
		for (i = 0; i < sl->sln; ++i) {
412
180480
			slc = sl->sublevels[i];
413
414
180480
			if (slc) {
415
1383
				slc->sorted = sl->tosort;
416
1383
				slc->start_position = sl->start_position;
417
1383
				sl->start_position += slc->tosort_num;
418
1383
				push_ls(slc);
419
1383
				sl->sublevels[i] = NULL;
420
1383
			}
421
		}
422
423
705
	} 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
749
	run_sort_cycle_st();
444
749
}
445
446
void
447
rxsort(struct sort_list_item **base, size_t nmemb)
448
{
449
	struct sort_level *sl;
450
451
1498
	sl = sort_calloc(1, sizeof(struct sort_level));
452
749
	sl->tosort = base;
453
749
	sl->tosort_num = nmemb;
454
749
	sl->tosort_sz = nmemb;
455
456
749
	run_top_sort_level(sl);
457
458
749
	free_sort_level(sl);
459
749
}