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