xref: /freebsd/usr.bin/sort/radixsort.c (revision 5e53a4f90f82c4345f277dd87cc9292f26e04a29)
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 ? */
54 static bool reverse_sort;
55 
56 /* sort sub-levels array size */
57 static const size_t slsz = 256 * sizeof(struct sort_level*);
58 
59 /* one sort level structure */
60 struct 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 */
77 struct level_stack {
78 	struct level_stack	 *next;
79 	struct sort_level	 *sl;
80 };
81 
82 static struct level_stack *g_ls;
83 
84 #if defined(SORT_THREADS)
85 /* stack guarding mutex */
86 static pthread_cond_t g_ls_cond;
87 static pthread_mutex_t g_ls_mutex;
88 
89 /* counter: how many items are left */
90 static size_t sort_left;
91 /* guarding mutex */
92 
93 /* semaphore to count threads */
94 static sem_t mtsem;
95 
96 /*
97  * Decrement items counter
98  */
99 static inline void
100 sort_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  */
114 static inline bool
115 have_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  */
133 static inline void
134 push_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  */
163 static inline struct sort_level*
164 pop_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  */
186 static inline struct sort_level*
187 pop_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 
218 static void
219 add_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 
244 static inline void
245 add_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 
256 static inline int
257 get_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 
270 static void
271 place_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 
285 static void
286 free_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 
315 static void
316 run_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 
478 end:
479 	free_sort_level(sl);
480 }
481 
482 /*
483  * Single-threaded sort cycle
484  */
485 static void
486 run_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  */
504 static void
505 run_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  */
520 static void*
521 sort_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 
531 static void
532 run_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 
642 static void
643 run_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 
692 void
693 rxsort(struct sort_list_item **base, size_t nmemb)
694 {
695 
696 	run_sort(base, nmemb);
697 }
698