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
sort_left_dec(size_t n)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
have_sort_left(void)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
push_ls(struct sort_level * sl)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*
pop_ls_st(void)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*
pop_ls_mt(void)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
add_to_sublevel(struct sort_level * sl,struct sort_list_item * item,size_t indx)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
add_leaf(struct sort_level * sl,struct sort_list_item * item)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
get_wc_index(struct sort_list_item * sli,size_t level)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
place_item(struct sort_level * sl,size_t item)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
free_sort_level(struct sort_level * sl)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
run_sort_level_next(struct sort_level * sl)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
run_sort_cycle_st(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
run_sort_cycle_mt(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*
sort_thread(void * arg)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
run_top_sort_level(struct sort_level * sl)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
run_sort(struct sort_list_item ** base,size_t nmemb)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
rxsort(struct sort_list_item ** base,size_t nmemb)693 rxsort(struct sort_list_item **base, size_t nmemb)
694 {
695
696 run_sort(base, nmemb);
697 }
698