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