radixsort.c revision 330449 
1/*-
2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
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 <sys/cdefs.h>
31__FBSDID("$FreeBSD: stable/11/usr.bin/sort/radixsort.c 330449 2018-03-05 07:26:05Z eadler $");
32
33#include <errno.h>
34#include <err.h>
35#include <langinfo.h>
36#include <math.h>
37#if defined(SORT_THREADS)
38#include <pthread.h>
39#include <semaphore.h>
40#endif
41#include <stdlib.h>
42#include <string.h>
43#include <wchar.h>
44#include <wctype.h>
45#include <unistd.h>
46
47#include "coll.h"
48#include "radixsort.h"
49
50#define DEFAULT_SORT_FUNC_RADIXSORT mergesort
51
52#define TINY_NODE(sl) ((sl)->tosort_num < 65)
53#define SMALL_NODE(sl) ((sl)->tosort_num < 5)
54
55/* are we sorting in reverse order ? */
56static bool reverse_sort;
57
58/* sort sub-levels array size */
59static const size_t slsz = 256 * sizeof(struct sort_level*);
60
61/* one sort level structure */
62struct sort_level
63{
64	struct sort_level	**sublevels;
65	struct sort_list_item	**leaves;
66	struct sort_list_item	**sorted;
67	struct sort_list_item	**tosort;
68	size_t			  leaves_num;
69	size_t			  leaves_sz;
70	size_t			  level;
71	size_t			  real_sln;
72	size_t			  start_position;
73	size_t			  sln;
74	size_t			  tosort_num;
75	size_t			  tosort_sz;
76};
77
78/* stack of sort levels ready to be sorted */
79struct level_stack {
80	struct level_stack	 *next;
81	struct sort_level	 *sl;
82};
83
84static struct level_stack *g_ls;
85
86#if defined(SORT_THREADS)
87/* stack guarding mutex */
88static pthread_cond_t g_ls_cond;
89static pthread_mutex_t g_ls_mutex;
90
91/* counter: how many items are left */
92static size_t sort_left;
93/* guarding mutex */
94
95/* semaphore to count threads */
96static sem_t mtsem;
97
98/*
99 * Decrement items counter
100 */
101static inline void
102sort_left_dec(size_t n)
103{
104	pthread_mutex_lock(&g_ls_mutex);
105	sort_left -= n;
106	if (sort_left == 0 && nthreads > 1)
107		pthread_cond_broadcast(&g_ls_cond);
108	pthread_mutex_unlock(&g_ls_mutex);
109}
110
111/*
112 * Do we have something to sort ?
113 *
114 * This routine does not need to be locked.
115 */
116static inline bool
117have_sort_left(void)
118{
119	bool ret;
120
121	ret = (sort_left > 0);
122
123	return (ret);
124}
125
126#else
127
128#define sort_left_dec(n)
129
130#endif /* SORT_THREADS */
131
132static void
133_push_ls(struct level_stack *ls)
134{
135
136	ls->next = g_ls;
137	g_ls = ls;
138}
139
140/*
141 * Push sort level to the stack
142 */
143static inline void
144push_ls(struct sort_level *sl)
145{
146	struct level_stack *new_ls;
147
148	new_ls = sort_malloc(sizeof(struct level_stack));
149	new_ls->sl = sl;
150
151#if defined(SORT_THREADS)
152	if (nthreads > 1) {
153		pthread_mutex_lock(&g_ls_mutex);
154		_push_ls(new_ls);
155		pthread_cond_signal(&g_ls_cond);
156		pthread_mutex_unlock(&g_ls_mutex);
157	} else
158#endif
159		_push_ls(new_ls);
160}
161
162/*
163 * Pop sort level from the stack (single-threaded style)
164 */
165static inline struct sort_level*
166pop_ls_st(void)
167{
168	struct sort_level *sl;
169
170	if (g_ls) {
171		struct level_stack *saved_ls;
172
173		sl = g_ls->sl;
174		saved_ls = g_ls;
175		g_ls = g_ls->next;
176		sort_free(saved_ls);
177	} else
178		sl = NULL;
179
180	return (sl);
181}
182
183#if defined(SORT_THREADS)
184
185/*
186 * Pop sort level from the stack (multi-threaded style)
187 */
188static inline struct sort_level*
189pop_ls_mt(void)
190{
191	struct level_stack *saved_ls;
192	struct sort_level *sl;
193
194	pthread_mutex_lock(&g_ls_mutex);
195
196	for (;;) {
197		if (g_ls) {
198			sl = g_ls->sl;
199			saved_ls = g_ls;
200			g_ls = g_ls->next;
201			break;
202		}
203		sl = NULL;
204		saved_ls = NULL;
205
206		if (have_sort_left() == 0)
207			break;
208		pthread_cond_wait(&g_ls_cond, &g_ls_mutex);
209	}
210
211	pthread_mutex_unlock(&g_ls_mutex);
212
213	sort_free(saved_ls);
214
215	return (sl);
216}
217
218#endif /* defined(SORT_THREADS) */
219
220static void
221add_to_sublevel(struct sort_level *sl, struct sort_list_item *item, size_t indx)
222{
223	struct sort_level *ssl;
224
225	ssl = sl->sublevels[indx];
226
227	if (ssl == NULL) {
228		ssl = sort_malloc(sizeof(struct sort_level));
229		memset(ssl, 0, sizeof(struct sort_level));
230
231		ssl->level = sl->level + 1;
232		sl->sublevels[indx] = ssl;
233
234		++(sl->real_sln);
235	}
236
237	if (++(ssl->tosort_num) > ssl->tosort_sz) {
238		ssl->tosort_sz = ssl->tosort_num + 128;
239		ssl->tosort = sort_realloc(ssl->tosort,
240		    sizeof(struct sort_list_item*) * (ssl->tosort_sz));
241	}
242
243	ssl->tosort[ssl->tosort_num - 1] = item;
244}
245
246static inline void
247add_leaf(struct sort_level *sl, struct sort_list_item *item)
248{
249
250	if (++(sl->leaves_num) > sl->leaves_sz) {
251		sl->leaves_sz = sl->leaves_num + 128;
252		sl->leaves = sort_realloc(sl->leaves,
253		    (sizeof(struct sort_list_item*) * (sl->leaves_sz)));
254	}
255	sl->leaves[sl->leaves_num - 1] = item;
256}
257
258static inline int
259get_wc_index(struct sort_list_item *sli, size_t level)
260{
261	const struct key_value *kv;
262	const struct bwstring *bws;
263
264	kv = get_key_from_keys_array(&sli->ka, 0);
265	bws = kv->k;
266
267	if ((BWSLEN(bws) > level))
268		return (unsigned char) BWS_GET(bws,level);
269	return (-1);
270}
271
272static void
273place_item(struct sort_level *sl, size_t item)
274{
275	struct sort_list_item *sli;
276	int c;
277
278	sli = sl->tosort[item];
279	c = get_wc_index(sli, sl->level);
280
281	if (c == -1)
282		add_leaf(sl, sli);
283	else
284		add_to_sublevel(sl, sli, c);
285}
286
287static void
288free_sort_level(struct sort_level *sl)
289{
290
291	if (sl) {
292		if (sl->leaves)
293			sort_free(sl->leaves);
294
295		if (sl->level > 0)
296			sort_free(sl->tosort);
297
298		if (sl->sublevels) {
299			struct sort_level *slc;
300			size_t sln;
301
302			sln = sl->sln;
303
304			for (size_t i = 0; i < sln; ++i) {
305				slc = sl->sublevels[i];
306				if (slc)
307					free_sort_level(slc);
308			}
309
310			sort_free(sl->sublevels);
311		}
312
313		sort_free(sl);
314	}
315}
316
317static void
318run_sort_level_next(struct sort_level *sl)
319{
320	struct sort_level *slc;
321	size_t i, sln, tosort_num;
322
323	if (sl->sublevels) {
324		sort_free(sl->sublevels);
325		sl->sublevels = NULL;
326	}
327
328	switch (sl->tosort_num) {
329	case 0:
330		goto end;
331	case (1):
332		sl->sorted[sl->start_position] = sl->tosort[0];
333		sort_left_dec(1);
334		goto end;
335	case (2):
336		if (list_coll_offset(&(sl->tosort[0]), &(sl->tosort[1]),
337		    sl->level) > 0) {
338			sl->sorted[sl->start_position++] = sl->tosort[1];
339			sl->sorted[sl->start_position] = sl->tosort[0];
340		} else {
341			sl->sorted[sl->start_position++] = sl->tosort[0];
342			sl->sorted[sl->start_position] = sl->tosort[1];
343		}
344		sort_left_dec(2);
345
346		goto end;
347	default:
348		if (TINY_NODE(sl) || (sl->level > 15)) {
349			listcoll_t func;
350
351			func = get_list_call_func(sl->level);
352
353			sl->leaves = sl->tosort;
354			sl->leaves_num = sl->tosort_num;
355			sl->leaves_sz = sl->leaves_num;
356			sl->leaves = sort_realloc(sl->leaves,
357			    (sizeof(struct sort_list_item *) *
358			    (sl->leaves_sz)));
359			sl->tosort = NULL;
360			sl->tosort_num = 0;
361			sl->tosort_sz = 0;
362			sl->sln = 0;
363			sl->real_sln = 0;
364			if (sort_opts_vals.sflag) {
365				if (mergesort(sl->leaves, sl->leaves_num,
366				    sizeof(struct sort_list_item *),
367				    (int(*)(const void *, const void *)) func) == -1)
368					/* NOTREACHED */
369					err(2, "Radix sort error 3");
370			} else
371				DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
372				    sizeof(struct sort_list_item *),
373				    (int(*)(const void *, const void *)) func);
374
375			memcpy(sl->sorted + sl->start_position,
376			    sl->leaves, sl->leaves_num *
377			    sizeof(struct sort_list_item*));
378
379			sort_left_dec(sl->leaves_num);
380
381			goto end;
382		} else {
383			sl->tosort_sz = sl->tosort_num;
384			sl->tosort = sort_realloc(sl->tosort,
385			    sizeof(struct sort_list_item*) * (sl->tosort_sz));
386		}
387	}
388
389	sl->sln = 256;
390	sl->sublevels = sort_malloc(slsz);
391	memset(sl->sublevels, 0, slsz);
392
393	sl->real_sln = 0;
394
395	tosort_num = sl->tosort_num;
396	for (i = 0; i < tosort_num; ++i)
397		place_item(sl, i);
398
399	sort_free(sl->tosort);
400	sl->tosort = NULL;
401	sl->tosort_num = 0;
402	sl->tosort_sz = 0;
403
404	if (sl->leaves_num > 1) {
405		if (keys_num > 1) {
406			if (sort_opts_vals.sflag) {
407				mergesort(sl->leaves, sl->leaves_num,
408				    sizeof(struct sort_list_item *),
409				    (int(*)(const void *, const void *)) list_coll);
410			} else {
411				DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
412				    sizeof(struct sort_list_item *),
413				    (int(*)(const void *, const void *)) list_coll);
414			}
415		} else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) {
416			DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
417			    sizeof(struct sort_list_item *),
418			    (int(*)(const void *, const void *)) list_coll_by_str_only);
419		}
420	}
421
422	sl->leaves_sz = sl->leaves_num;
423	sl->leaves = sort_realloc(sl->leaves, (sizeof(struct sort_list_item *) *
424	    (sl->leaves_sz)));
425
426	if (!reverse_sort) {
427		memcpy(sl->sorted + sl->start_position, sl->leaves,
428		    sl->leaves_num * sizeof(struct sort_list_item*));
429		sl->start_position += sl->leaves_num;
430		sort_left_dec(sl->leaves_num);
431
432		sort_free(sl->leaves);
433		sl->leaves = NULL;
434		sl->leaves_num = 0;
435		sl->leaves_sz = 0;
436
437		sln = sl->sln;
438
439		for (i = 0; i < sln; ++i) {
440			slc = sl->sublevels[i];
441
442			if (slc) {
443				slc->sorted = sl->sorted;
444				slc->start_position = sl->start_position;
445				sl->start_position += slc->tosort_num;
446				if (SMALL_NODE(slc))
447					run_sort_level_next(slc);
448				else
449					push_ls(slc);
450				sl->sublevels[i] = NULL;
451			}
452		}
453
454	} else {
455		size_t n;
456
457		sln = sl->sln;
458
459		for (i = 0; i < sln; ++i) {
460			n = sln - i - 1;
461			slc = sl->sublevels[n];
462
463			if (slc) {
464				slc->sorted = sl->sorted;
465				slc->start_position = sl->start_position;
466				sl->start_position += slc->tosort_num;
467				if (SMALL_NODE(slc))
468					run_sort_level_next(slc);
469				else
470					push_ls(slc);
471				sl->sublevels[n] = NULL;
472			}
473		}
474
475		memcpy(sl->sorted + sl->start_position, sl->leaves,
476		    sl->leaves_num * sizeof(struct sort_list_item*));
477		sort_left_dec(sl->leaves_num);
478	}
479
480end:
481	free_sort_level(sl);
482}
483
484/*
485 * Single-threaded sort cycle
486 */
487static void
488run_sort_cycle_st(void)
489{
490	struct sort_level *slc;
491
492	for (;;) {
493		slc = pop_ls_st();
494		if (slc == NULL) {
495			break;
496		}
497		run_sort_level_next(slc);
498	}
499}
500
501#if defined(SORT_THREADS)
502
503/*
504 * Multi-threaded sort cycle
505 */
506static void
507run_sort_cycle_mt(void)
508{
509	struct sort_level *slc;
510
511	for (;;) {
512		slc = pop_ls_mt();
513		if (slc == NULL)
514			break;
515		run_sort_level_next(slc);
516	}
517}
518
519/*
520 * Sort cycle thread (in multi-threaded mode)
521 */
522static void*
523sort_thread(void* arg)
524{
525	run_sort_cycle_mt();
526	sem_post(&mtsem);
527
528	return (arg);
529}
530
531#endif /* defined(SORT_THREADS) */
532
533static void
534run_top_sort_level(struct sort_level *sl)
535{
536	struct sort_level *slc;
537
538	reverse_sort = sort_opts_vals.kflag ? keys[0].sm.rflag :
539	    default_sort_mods->rflag;
540
541	sl->start_position = 0;
542	sl->sln = 256;
543	sl->sublevels = sort_malloc(slsz);
544	memset(sl->sublevels, 0, slsz);
545
546	for (size_t i = 0; i < sl->tosort_num; ++i)
547		place_item(sl, i);
548
549	if (sl->leaves_num > 1) {
550		if (keys_num > 1) {
551			if (sort_opts_vals.sflag) {
552				mergesort(sl->leaves, sl->leaves_num,
553				    sizeof(struct sort_list_item *),
554				    (int(*)(const void *, const void *)) list_coll);
555			} else {
556				DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
557				    sizeof(struct sort_list_item *),
558				    (int(*)(const void *, const void *)) list_coll);
559			}
560		} else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) {
561			DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
562			    sizeof(struct sort_list_item *),
563			    (int(*)(const void *, const void *)) list_coll_by_str_only);
564		}
565	}
566
567	if (!reverse_sort) {
568		memcpy(sl->tosort + sl->start_position, sl->leaves,
569		    sl->leaves_num * sizeof(struct sort_list_item*));
570		sl->start_position += sl->leaves_num;
571		sort_left_dec(sl->leaves_num);
572
573		for (size_t i = 0; i < sl->sln; ++i) {
574			slc = sl->sublevels[i];
575
576			if (slc) {
577				slc->sorted = sl->tosort;
578				slc->start_position = sl->start_position;
579				sl->start_position += slc->tosort_num;
580				push_ls(slc);
581				sl->sublevels[i] = NULL;
582			}
583		}
584
585	} else {
586		size_t n;
587
588		for (size_t i = 0; i < sl->sln; ++i) {
589
590			n = sl->sln - i - 1;
591			slc = sl->sublevels[n];
592
593			if (slc) {
594				slc->sorted = sl->tosort;
595				slc->start_position = sl->start_position;
596				sl->start_position += slc->tosort_num;
597				push_ls(slc);
598				sl->sublevels[n] = NULL;
599			}
600		}
601
602		memcpy(sl->tosort + sl->start_position, sl->leaves,
603		    sl->leaves_num * sizeof(struct sort_list_item*));
604
605		sort_left_dec(sl->leaves_num);
606	}
607
608#if defined(SORT_THREADS)
609	if (nthreads < 2) {
610#endif
611		run_sort_cycle_st();
612#if defined(SORT_THREADS)
613	} else {
614		size_t i;
615
616		for(i = 0; i < nthreads; ++i) {
617			pthread_attr_t attr;
618			pthread_t pth;
619
620			pthread_attr_init(&attr);
621			pthread_attr_setdetachstate(&attr, PTHREAD_DETACHED);
622
623			for (;;) {
624				int res = pthread_create(&pth, &attr,
625				    sort_thread, NULL);
626				if (res >= 0)
627					break;
628				if (errno == EAGAIN) {
629					pthread_yield();
630					continue;
631				}
632				err(2, NULL);
633			}
634
635			pthread_attr_destroy(&attr);
636		}
637
638		for (i = 0; i < nthreads; ++i)
639			sem_wait(&mtsem);
640	}
641#endif /* defined(SORT_THREADS) */
642}
643
644static void
645run_sort(struct sort_list_item **base, size_t nmemb)
646{
647	struct sort_level *sl;
648
649#if defined(SORT_THREADS)
650	size_t nthreads_save = nthreads;
651	if (nmemb < MT_SORT_THRESHOLD)
652		nthreads = 1;
653
654	if (nthreads > 1) {
655		pthread_mutexattr_t mattr;
656
657		pthread_mutexattr_init(&mattr);
658		pthread_mutexattr_settype(&mattr, PTHREAD_MUTEX_ADAPTIVE_NP);
659
660		pthread_mutex_init(&g_ls_mutex, &mattr);
661		pthread_cond_init(&g_ls_cond, NULL);
662
663		pthread_mutexattr_destroy(&mattr);
664
665		sem_init(&mtsem, 0, 0);
666
667	}
668#endif
669
670	sl = sort_malloc(sizeof(struct sort_level));
671	memset(sl, 0, sizeof(struct sort_level));
672
673	sl->tosort = base;
674	sl->tosort_num = nmemb;
675	sl->tosort_sz = nmemb;
676
677#if defined(SORT_THREADS)
678	sort_left = nmemb;
679#endif
680
681	run_top_sort_level(sl);
682
683	free_sort_level(sl);
684
685#if defined(SORT_THREADS)
686	if (nthreads > 1) {
687		sem_destroy(&mtsem);
688		pthread_mutex_destroy(&g_ls_mutex);
689	}
690	nthreads = nthreads_save;
691#endif
692}
693
694void
695rxsort(struct sort_list_item **base, size_t nmemb)
696{
697
698	run_sort(base, nmemb);
699}
700