xref: /dragonfly/usr.bin/sort/radixsort.c (revision e98bdfd3) 
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_mutex_t g_ls_mutex;
87 
88 /* counter: how many items are left */
89 static size_t sort_left;
90 /* guarding mutex */
91 static pthread_mutex_t sort_left_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 
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  */
111 static inline bool
112 have_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  */
131 static inline void
132 push_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  */
156 static inline struct sort_level*
157 pop_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  */
179 static inline struct sort_level*
180 pop_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 
205 static void
206 add_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 
231 static inline void
232 add_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 
243 static inline int
244 get_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 
255 static void
256 place_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 
270 static void
271 free_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 
300 static void
301 run_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 
463 end:
464 	free_sort_level(sl);
465 }
466 
467 /*
468  * Single-threaded sort cycle
469  */
470 static void
471 run_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  */
489 static void
490 run_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  */
510 static void*
511 sort_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 
523 static void
524 run_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 
635 static void
636 run_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_ERRORCHECK);
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 
686 void
687 rxsort(struct sort_list_item **base, size_t nmemb)
688 {
689 
690 	run_sort(base, nmemb);
691 }
692