radixsort.c revision 318152 
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 318152 2017-05-10 20:29:01Z marius $");
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 key_value *kv;
260	const struct bwstring *bws;
261
262	kv = get_key_from_keys_array(&sli->ka, 0);
263	bws = kv->k;
264
265	if ((BWSLEN(bws) > level))
266		return (unsigned char) BWS_GET(bws,level);
267	return (-1);
268}
269
270static void
271place_item(struct sort_level *sl, size_t item)
272{
273	struct sort_list_item *sli;
274	int c;
275
276	sli = sl->tosort[item];
277	c = get_wc_index(sli, sl->level);
278
279	if (c == -1)
280		add_leaf(sl, sli);
281	else
282		add_to_sublevel(sl, sli, c);
283}
284
285static void
286free_sort_level(struct sort_level *sl)
287{
288
289	if (sl) {
290		if (sl->leaves)
291			sort_free(sl->leaves);
292
293		if (sl->level > 0)
294			sort_free(sl->tosort);
295
296		if (sl->sublevels) {
297			struct sort_level *slc;
298			size_t sln;
299
300			sln = sl->sln;
301
302			for (size_t i = 0; i < sln; ++i) {
303				slc = sl->sublevels[i];
304				if (slc)
305					free_sort_level(slc);
306			}
307
308			sort_free(sl->sublevels);
309		}
310
311		sort_free(sl);
312	}
313}
314
315static void
316run_sort_level_next(struct sort_level *sl)
317{
318	struct sort_level *slc;
319	size_t i, sln, tosort_num;
320
321	if (sl->sublevels) {
322		sort_free(sl->sublevels);
323		sl->sublevels = NULL;
324	}
325
326	switch (sl->tosort_num){
327	case 0:
328		goto end;
329	case (1):
330		sl->sorted[sl->start_position] = sl->tosort[0];
331		sort_left_dec(1);
332		goto end;
333	case (2):
334		if (list_coll_offset(&(sl->tosort[0]), &(sl->tosort[1]),
335		    sl->level) > 0) {
336			sl->sorted[sl->start_position++] = sl->tosort[1];
337			sl->sorted[sl->start_position] = sl->tosort[0];
338		} else {
339			sl->sorted[sl->start_position++] = sl->tosort[0];
340			sl->sorted[sl->start_position] = sl->tosort[1];
341		}
342		sort_left_dec(2);
343
344		goto end;
345	default:
346		if (TINY_NODE(sl) || (sl->level > 15)) {
347			listcoll_t func;
348
349			func = get_list_call_func(sl->level);
350
351			sl->leaves = sl->tosort;
352			sl->leaves_num = sl->tosort_num;
353			sl->leaves_sz = sl->leaves_num;
354			sl->leaves = sort_realloc(sl->leaves,
355			    (sizeof(struct sort_list_item *) *
356			    (sl->leaves_sz)));
357			sl->tosort = NULL;
358			sl->tosort_num = 0;
359			sl->tosort_sz = 0;
360			sl->sln = 0;
361			sl->real_sln = 0;
362			if (sort_opts_vals.sflag) {
363				if (mergesort(sl->leaves, sl->leaves_num,
364				    sizeof(struct sort_list_item *),
365				    (int(*)(const void *, const void *)) func) == -1)
366					/* NOTREACHED */
367					err(2, "Radix sort error 3");
368			} else
369				DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
370				    sizeof(struct sort_list_item *),
371				    (int(*)(const void *, const void *)) func);
372
373			memcpy(sl->sorted + sl->start_position,
374			    sl->leaves, sl->leaves_num *
375			    sizeof(struct sort_list_item*));
376
377			sort_left_dec(sl->leaves_num);
378
379			goto end;
380		} else {
381			sl->tosort_sz = sl->tosort_num;
382			sl->tosort = sort_realloc(sl->tosort,
383			    sizeof(struct sort_list_item*) * (sl->tosort_sz));
384		}
385	}
386
387	sl->sln = 256;
388	sl->sublevels = sort_malloc(slsz);
389	memset(sl->sublevels, 0, slsz);
390
391	sl->real_sln = 0;
392
393	tosort_num = sl->tosort_num;
394	for (i = 0; i < tosort_num; ++i)
395		place_item(sl, i);
396
397	sort_free(sl->tosort);
398	sl->tosort = NULL;
399	sl->tosort_num = 0;
400	sl->tosort_sz = 0;
401
402	if (sl->leaves_num > 1) {
403		if (keys_num > 1) {
404			if (sort_opts_vals.sflag) {
405				mergesort(sl->leaves, sl->leaves_num,
406				    sizeof(struct sort_list_item *),
407				    (int(*)(const void *, const void *)) list_coll);
408			} else {
409				DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
410				    sizeof(struct sort_list_item *),
411				    (int(*)(const void *, const void *)) list_coll);
412			}
413		} else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) {
414			DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
415			    sizeof(struct sort_list_item *),
416			    (int(*)(const void *, const void *)) list_coll_by_str_only);
417		}
418	}
419
420	sl->leaves_sz = sl->leaves_num;
421	sl->leaves = sort_realloc(sl->leaves, (sizeof(struct sort_list_item *) *
422	    (sl->leaves_sz)));
423
424	if (!reverse_sort) {
425		memcpy(sl->sorted + sl->start_position, sl->leaves,
426		    sl->leaves_num * sizeof(struct sort_list_item*));
427		sl->start_position += sl->leaves_num;
428		sort_left_dec(sl->leaves_num);
429
430		sort_free(sl->leaves);
431		sl->leaves = NULL;
432		sl->leaves_num = 0;
433		sl->leaves_sz = 0;
434
435		sln = sl->sln;
436
437		for (i = 0; i < sln; ++i) {
438			slc = sl->sublevels[i];
439
440			if (slc) {
441				slc->sorted = sl->sorted;
442				slc->start_position = sl->start_position;
443				sl->start_position += slc->tosort_num;
444				if (SMALL_NODE(slc))
445					run_sort_level_next(slc);
446				else
447					push_ls(slc);
448				sl->sublevels[i] = NULL;
449			}
450		}
451
452	} else {
453		size_t n;
454
455		sln = sl->sln;
456
457		for (i = 0; i < sln; ++i) {
458			n = sln - i - 1;
459			slc = sl->sublevels[n];
460
461			if (slc) {
462				slc->sorted = sl->sorted;
463				slc->start_position = sl->start_position;
464				sl->start_position += slc->tosort_num;
465				if (SMALL_NODE(slc))
466					run_sort_level_next(slc);
467				else
468					push_ls(slc);
469				sl->sublevels[n] = NULL;
470			}
471		}
472
473		memcpy(sl->sorted + sl->start_position, sl->leaves,
474		    sl->leaves_num * sizeof(struct sort_list_item*));
475		sort_left_dec(sl->leaves_num);
476	}
477
478end:
479	free_sort_level(sl);
480}
481
482/*
483 * Single-threaded sort cycle
484 */
485static void
486run_sort_cycle_st(void)
487{
488	struct sort_level *slc;
489
490	for (;;) {
491		slc = pop_ls_st();
492		if (slc == NULL) {
493			break;
494		}
495		run_sort_level_next(slc);
496	}
497}
498
499#if defined(SORT_THREADS)
500
501/*
502 * Multi-threaded sort cycle
503 */
504static void
505run_sort_cycle_mt(void)
506{
507	struct sort_level *slc;
508
509	for (;;) {
510		slc = pop_ls_mt();
511		if (slc == NULL)
512			break;
513		run_sort_level_next(slc);
514	}
515}
516
517/*
518 * Sort cycle thread (in multi-threaded mode)
519 */
520static void*
521sort_thread(void* arg)
522{
523	run_sort_cycle_mt();
524	sem_post(&mtsem);
525
526	return (arg);
527}
528
529#endif /* defined(SORT_THREADS) */
530
531static void
532run_top_sort_level(struct sort_level *sl)
533{
534	struct sort_level *slc;
535
536	reverse_sort = sort_opts_vals.kflag ? keys[0].sm.rflag :
537	    default_sort_mods->rflag;
538
539	sl->start_position = 0;
540	sl->sln = 256;
541	sl->sublevels = sort_malloc(slsz);
542	memset(sl->sublevels, 0, slsz);
543
544	for (size_t i = 0; i < sl->tosort_num; ++i)
545		place_item(sl, i);
546
547	if (sl->leaves_num > 1) {
548		if (keys_num > 1) {
549			if (sort_opts_vals.sflag) {
550				mergesort(sl->leaves, sl->leaves_num,
551				    sizeof(struct sort_list_item *),
552				    (int(*)(const void *, const void *)) list_coll);
553			} else {
554				DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
555				    sizeof(struct sort_list_item *),
556				    (int(*)(const void *, const void *)) list_coll);
557			}
558		} else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) {
559			DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
560			    sizeof(struct sort_list_item *),
561			    (int(*)(const void *, const void *)) list_coll_by_str_only);
562		}
563	}
564
565	if (!reverse_sort) {
566		memcpy(sl->tosort + sl->start_position, sl->leaves,
567		    sl->leaves_num * sizeof(struct sort_list_item*));
568		sl->start_position += sl->leaves_num;
569		sort_left_dec(sl->leaves_num);
570
571		for (size_t i = 0; i < sl->sln; ++i) {
572			slc = sl->sublevels[i];
573
574			if (slc) {
575				slc->sorted = sl->tosort;
576				slc->start_position = sl->start_position;
577				sl->start_position += slc->tosort_num;
578				push_ls(slc);
579				sl->sublevels[i] = NULL;
580			}
581		}
582
583	} else {
584		size_t n;
585
586		for (size_t i = 0; i < sl->sln; ++i) {
587
588			n = sl->sln - i - 1;
589			slc = sl->sublevels[n];
590
591			if (slc) {
592				slc->sorted = sl->tosort;
593				slc->start_position = sl->start_position;
594				sl->start_position += slc->tosort_num;
595				push_ls(slc);
596				sl->sublevels[n] = NULL;
597			}
598		}
599
600		memcpy(sl->tosort + sl->start_position, sl->leaves,
601		    sl->leaves_num * sizeof(struct sort_list_item*));
602
603		sort_left_dec(sl->leaves_num);
604	}
605
606#if defined(SORT_THREADS)
607	if (nthreads < 2) {
608#endif
609		run_sort_cycle_st();
610#if defined(SORT_THREADS)
611	} else {
612		size_t i;
613
614		for(i = 0; i < nthreads; ++i) {
615			pthread_attr_t attr;
616			pthread_t pth;
617
618			pthread_attr_init(&attr);
619			pthread_attr_setdetachstate(&attr, PTHREAD_DETACHED);
620
621			for (;;) {
622				int res = pthread_create(&pth, &attr,
623				    sort_thread, NULL);
624				if (res >= 0)
625					break;
626				if (errno == EAGAIN) {
627					pthread_yield();
628					continue;
629				}
630				err(2, NULL);
631			}
632
633			pthread_attr_destroy(&attr);
634		}
635
636		for (i = 0; i < nthreads; ++i)
637			sem_wait(&mtsem);
638	}
639#endif /* defined(SORT_THREADS) */
640}
641
642static void
643run_sort(struct sort_list_item **base, size_t nmemb)
644{
645	struct sort_level *sl;
646
647#if defined(SORT_THREADS)
648	size_t nthreads_save = nthreads;
649	if (nmemb < MT_SORT_THRESHOLD)
650		nthreads = 1;
651
652	if (nthreads > 1) {
653		pthread_mutexattr_t mattr;
654
655		pthread_mutexattr_init(&mattr);
656		pthread_mutexattr_settype(&mattr, PTHREAD_MUTEX_ADAPTIVE_NP);
657
658		pthread_mutex_init(&g_ls_mutex, &mattr);
659		pthread_cond_init(&g_ls_cond, NULL);
660
661		pthread_mutexattr_destroy(&mattr);
662
663		sem_init(&mtsem, 0, 0);
664
665	}
666#endif
667
668	sl = sort_malloc(sizeof(struct sort_level));
669	memset(sl, 0, sizeof(struct sort_level));
670
671	sl->tosort = base;
672	sl->tosort_num = nmemb;
673	sl->tosort_sz = nmemb;
674
675#if defined(SORT_THREADS)
676	sort_left = nmemb;
677#endif
678
679	run_top_sort_level(sl);
680
681	free_sort_level(sl);
682
683#if defined(SORT_THREADS)
684	if (nthreads > 1) {
685		sem_destroy(&mtsem);
686		pthread_mutex_destroy(&g_ls_mutex);
687	}
688	nthreads = nthreads_save;
689#endif
690}
691
692void
693rxsort(struct sort_list_item **base, size_t nmemb)
694{
695
696	run_sort(base, nmemb);
697}
698