xref: /dragonfly/usr.bin/sort/radixsort.c (revision dd491ed2) 
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  * $FreeBSD: head/usr.bin/sort/radixsort.c 281133 2015-04-06 03:02:20Z pfg $
28  */
29 
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 	}
107 	pthread_mutex_unlock(&g_ls_mutex);
108 }
109 
110 /*
111  * Do we have something to sort ?
112  *
113  * This routine does not need to be locked.
114  */
115 static inline bool
116 have_sort_left(void)
117 {
118 	bool ret;
119 
120 	ret = (sort_left > 0);
121 
122 	return (ret);
123 }
124 
125 #else
126 
127 #define sort_left_dec(n)
128 
129 #endif /* SORT_THREADS */
130 
131 /*
132  * Push sort level to the stack
133  */
134 static inline void
135 push_ls(struct sort_level *sl)
136 {
137 	struct level_stack *new_ls;
138 
139 	new_ls = sort_malloc(sizeof(struct level_stack));
140 	new_ls->sl = sl;
141 
142 #if defined(SORT_THREADS)
143 	if (nthreads > 1)
144 		pthread_mutex_lock(&g_ls_mutex);
145 #endif
146 
147 	new_ls->next = g_ls;
148 	g_ls = new_ls;
149 
150 #if defined(SORT_THREADS)
151 	if (nthreads > 1) {
152 		pthread_cond_signal(&g_ls_cond);
153 	}
154 #endif
155 
156 #if defined(SORT_THREADS)
157 	if (nthreads > 1)
158 		pthread_mutex_unlock(&g_ls_mutex);
159 #endif
160 }
161 
162 /*
163  * Pop sort level from the stack (single-threaded style)
164  */
165 static inline struct sort_level*
166 pop_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  */
188 static inline struct sort_level*
189 pop_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 
220 static void
221 add_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 
246 static inline void
247 add_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 
258 static inline int
259 get_wc_index(struct sort_list_item *sli, size_t level)
260 {
261 	const struct bwstring *bws;
262 
263 	bws = sli->ka.key[0].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_ERRORCHECK);
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