1 /*-
2 * SPDX-License-Identifier: BSD-2-Clause
3 *
4 * Copyright (C) 2012 Oleg Moskalenko <mom040267@gmail.com>
5 * Copyright (C) 2012 Gabor Kovesdan <gabor@FreeBSD.org>
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 */
29
30 #include <sys/cdefs.h>
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 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
have_sort_left(void)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 static void
_push_ls(struct level_stack * ls)131 _push_ls(struct level_stack *ls)
132 {
133
134 ls->next = g_ls;
135 g_ls = ls;
136 }
137
138 /*
139 * Push sort level to the stack
140 */
141 static inline void
push_ls(struct sort_level * sl)142 push_ls(struct sort_level *sl)
143 {
144 struct level_stack *new_ls;
145
146 new_ls = sort_malloc(sizeof(struct level_stack));
147 new_ls->sl = sl;
148
149 #if defined(SORT_THREADS)
150 if (nthreads > 1) {
151 pthread_mutex_lock(&g_ls_mutex);
152 _push_ls(new_ls);
153 pthread_cond_signal(&g_ls_cond);
154 pthread_mutex_unlock(&g_ls_mutex);
155 } else
156 #endif
157 _push_ls(new_ls);
158 }
159
160 /*
161 * Pop sort level from the stack (single-threaded style)
162 */
163 static inline struct sort_level*
pop_ls_st(void)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*
pop_ls_mt(void)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
add_to_sublevel(struct sort_level * sl,struct sort_list_item * item,size_t indx)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_calloc(1, sizeof(struct sort_level));
227
228 ssl->level = sl->level + 1;
229 sl->sublevels[indx] = ssl;
230
231 ++(sl->real_sln);
232 }
233
234 if (++(ssl->tosort_num) > ssl->tosort_sz) {
235 ssl->tosort_sz = ssl->tosort_num + 128;
236 ssl->tosort = sort_realloc(ssl->tosort,
237 sizeof(struct sort_list_item*) * (ssl->tosort_sz));
238 }
239
240 ssl->tosort[ssl->tosort_num - 1] = item;
241 }
242
243 static inline void
add_leaf(struct sort_level * sl,struct sort_list_item * item)244 add_leaf(struct sort_level *sl, struct sort_list_item *item)
245 {
246
247 if (++(sl->leaves_num) > sl->leaves_sz) {
248 sl->leaves_sz = sl->leaves_num + 128;
249 sl->leaves = sort_realloc(sl->leaves,
250 (sizeof(struct sort_list_item*) * (sl->leaves_sz)));
251 }
252 sl->leaves[sl->leaves_num - 1] = item;
253 }
254
255 static inline int
get_wc_index(struct sort_list_item * sli,size_t level)256 get_wc_index(struct sort_list_item *sli, size_t level)
257 {
258 const size_t wcfact = (mb_cur_max == 1) ? 1 : sizeof(wchar_t);
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) * wcfact > level)) {
266 wchar_t res;
267
268 /*
269 * Sort wchar strings a byte at a time, rather than a single
270 * byte from each wchar.
271 */
272 res = (wchar_t)BWS_GET(bws, level / wcfact);
273 /* Sort most-significant byte first. */
274 if (level % wcfact < wcfact - 1)
275 res = (res >> (8 * (wcfact - 1 - (level % wcfact))));
276
277 return (res & 0xff);
278 }
279
280 return (-1);
281 }
282
283 static void
place_item(struct sort_level * sl,size_t item)284 place_item(struct sort_level *sl, size_t item)
285 {
286 struct sort_list_item *sli;
287 int c;
288
289 sli = sl->tosort[item];
290 c = get_wc_index(sli, sl->level);
291
292 if (c == -1)
293 add_leaf(sl, sli);
294 else
295 add_to_sublevel(sl, sli, c);
296 }
297
298 static void
free_sort_level(struct sort_level * sl)299 free_sort_level(struct sort_level *sl)
300 {
301
302 if (sl) {
303 if (sl->leaves)
304 sort_free(sl->leaves);
305
306 if (sl->level > 0)
307 sort_free(sl->tosort);
308
309 if (sl->sublevels) {
310 struct sort_level *slc;
311 size_t sln;
312
313 sln = sl->sln;
314
315 for (size_t i = 0; i < sln; ++i) {
316 slc = sl->sublevels[i];
317 if (slc)
318 free_sort_level(slc);
319 }
320
321 sort_free(sl->sublevels);
322 }
323
324 sort_free(sl);
325 }
326 }
327
328 static void
run_sort_level_next(struct sort_level * sl)329 run_sort_level_next(struct sort_level *sl)
330 {
331 const size_t wcfact = (mb_cur_max == 1) ? 1 : sizeof(wchar_t);
332 struct sort_level *slc;
333 size_t i, sln, tosort_num;
334
335 if (sl->sublevels) {
336 sort_free(sl->sublevels);
337 sl->sublevels = NULL;
338 }
339
340 switch (sl->tosort_num) {
341 case 0:
342 goto end;
343 case (1):
344 sl->sorted[sl->start_position] = sl->tosort[0];
345 sort_left_dec(1);
346 goto end;
347 case (2):
348 /*
349 * Radixsort only processes a single byte at a time. In wchar
350 * mode, this can be a subset of the length of a character.
351 * list_coll_offset() offset is in units of wchar, not bytes.
352 * So to calculate the offset, we must divide by
353 * sizeof(wchar_t) and round down to the index of the first
354 * character this level references.
355 */
356 if (list_coll_offset(&(sl->tosort[0]), &(sl->tosort[1]),
357 sl->level / wcfact) > 0) {
358 sl->sorted[sl->start_position++] = sl->tosort[1];
359 sl->sorted[sl->start_position] = sl->tosort[0];
360 } else {
361 sl->sorted[sl->start_position++] = sl->tosort[0];
362 sl->sorted[sl->start_position] = sl->tosort[1];
363 }
364 sort_left_dec(2);
365
366 goto end;
367 default:
368 if (TINY_NODE(sl) || (sl->level > 15)) {
369 listcoll_t func;
370
371 /*
372 * Collate comparison offset is in units of
373 * character-width, so we must divide the level (bytes)
374 * by operating character width (wchar_t or char). See
375 * longer comment above.
376 */
377 func = get_list_call_func(sl->level / wcfact);
378
379 sl->leaves = sl->tosort;
380 sl->leaves_num = sl->tosort_num;
381 sl->leaves_sz = sl->leaves_num;
382 sl->leaves = sort_realloc(sl->leaves,
383 (sizeof(struct sort_list_item *) *
384 (sl->leaves_sz)));
385 sl->tosort = NULL;
386 sl->tosort_num = 0;
387 sl->tosort_sz = 0;
388 sl->sln = 0;
389 sl->real_sln = 0;
390 if (sort_opts_vals.sflag) {
391 if (mergesort(sl->leaves, sl->leaves_num,
392 sizeof(struct sort_list_item *),
393 (int(*)(const void *, const void *)) func) == -1)
394 /* NOTREACHED */
395 err(2, "Radix sort error 3");
396 } else
397 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
398 sizeof(struct sort_list_item *),
399 (int(*)(const void *, const void *)) func);
400
401 memcpy(sl->sorted + sl->start_position,
402 sl->leaves, sl->leaves_num *
403 sizeof(struct sort_list_item*));
404
405 sort_left_dec(sl->leaves_num);
406
407 goto end;
408 } else {
409 sl->tosort_sz = sl->tosort_num;
410 sl->tosort = sort_realloc(sl->tosort,
411 sizeof(struct sort_list_item*) * (sl->tosort_sz));
412 }
413 }
414
415 sl->sln = 256;
416 sl->sublevels = sort_calloc(1, slsz);
417
418 sl->real_sln = 0;
419
420 tosort_num = sl->tosort_num;
421 for (i = 0; i < tosort_num; ++i)
422 place_item(sl, i);
423
424 sort_free(sl->tosort);
425 sl->tosort = NULL;
426 sl->tosort_num = 0;
427 sl->tosort_sz = 0;
428
429 if (sl->leaves_num > 1) {
430 if (keys_num > 1) {
431 if (sort_opts_vals.sflag) {
432 mergesort(sl->leaves, sl->leaves_num,
433 sizeof(struct sort_list_item *),
434 (int(*)(const void *, const void *)) list_coll);
435 } else {
436 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
437 sizeof(struct sort_list_item *),
438 (int(*)(const void *, const void *)) list_coll);
439 }
440 } else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) {
441 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
442 sizeof(struct sort_list_item *),
443 (int(*)(const void *, const void *)) list_coll_by_str_only);
444 }
445 }
446
447 sl->leaves_sz = sl->leaves_num;
448 sl->leaves = sort_realloc(sl->leaves, (sizeof(struct sort_list_item *) *
449 (sl->leaves_sz)));
450
451 if (!reverse_sort) {
452 memcpy(sl->sorted + sl->start_position, sl->leaves,
453 sl->leaves_num * sizeof(struct sort_list_item*));
454 sl->start_position += sl->leaves_num;
455 sort_left_dec(sl->leaves_num);
456
457 sort_free(sl->leaves);
458 sl->leaves = NULL;
459 sl->leaves_num = 0;
460 sl->leaves_sz = 0;
461
462 sln = sl->sln;
463
464 for (i = 0; i < sln; ++i) {
465 slc = sl->sublevels[i];
466
467 if (slc) {
468 slc->sorted = sl->sorted;
469 slc->start_position = sl->start_position;
470 sl->start_position += slc->tosort_num;
471 if (SMALL_NODE(slc))
472 run_sort_level_next(slc);
473 else
474 push_ls(slc);
475 sl->sublevels[i] = NULL;
476 }
477 }
478
479 } else {
480 size_t n;
481
482 sln = sl->sln;
483
484 for (i = 0; i < sln; ++i) {
485 n = sln - i - 1;
486 slc = sl->sublevels[n];
487
488 if (slc) {
489 slc->sorted = sl->sorted;
490 slc->start_position = sl->start_position;
491 sl->start_position += slc->tosort_num;
492 if (SMALL_NODE(slc))
493 run_sort_level_next(slc);
494 else
495 push_ls(slc);
496 sl->sublevels[n] = NULL;
497 }
498 }
499
500 memcpy(sl->sorted + sl->start_position, sl->leaves,
501 sl->leaves_num * sizeof(struct sort_list_item*));
502 sort_left_dec(sl->leaves_num);
503 }
504
505 end:
506 free_sort_level(sl);
507 }
508
509 /*
510 * Single-threaded sort cycle
511 */
512 static void
run_sort_cycle_st(void)513 run_sort_cycle_st(void)
514 {
515 struct sort_level *slc;
516
517 for (;;) {
518 slc = pop_ls_st();
519 if (slc == NULL) {
520 break;
521 }
522 run_sort_level_next(slc);
523 }
524 }
525
526 #if defined(SORT_THREADS)
527
528 /*
529 * Multi-threaded sort cycle
530 */
531 static void
run_sort_cycle_mt(void)532 run_sort_cycle_mt(void)
533 {
534 struct sort_level *slc;
535
536 for (;;) {
537 slc = pop_ls_mt();
538 if (slc == NULL)
539 break;
540 run_sort_level_next(slc);
541 }
542 }
543
544 /*
545 * Sort cycle thread (in multi-threaded mode)
546 */
547 static void*
sort_thread(void * arg)548 sort_thread(void* arg)
549 {
550 run_sort_cycle_mt();
551 sem_post(&mtsem);
552
553 return (arg);
554 }
555
556 #endif /* defined(SORT_THREADS) */
557
558 static void
run_top_sort_level(struct sort_level * sl)559 run_top_sort_level(struct sort_level *sl)
560 {
561 struct sort_level *slc;
562
563 reverse_sort = sort_opts_vals.kflag ? keys[0].sm.rflag :
564 default_sort_mods->rflag;
565
566 sl->start_position = 0;
567 sl->sln = 256;
568 sl->sublevels = sort_calloc(1, slsz);
569
570 for (size_t i = 0; i < sl->tosort_num; ++i)
571 place_item(sl, i);
572
573 if (sl->leaves_num > 1) {
574 if (keys_num > 1) {
575 if (sort_opts_vals.sflag) {
576 mergesort(sl->leaves, sl->leaves_num,
577 sizeof(struct sort_list_item *),
578 (int(*)(const void *, const void *)) list_coll);
579 } else {
580 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
581 sizeof(struct sort_list_item *),
582 (int(*)(const void *, const void *)) list_coll);
583 }
584 } else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) {
585 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
586 sizeof(struct sort_list_item *),
587 (int(*)(const void *, const void *)) list_coll_by_str_only);
588 }
589 }
590
591 if (!reverse_sort) {
592 memcpy(sl->tosort + sl->start_position, sl->leaves,
593 sl->leaves_num * sizeof(struct sort_list_item*));
594 sl->start_position += sl->leaves_num;
595 sort_left_dec(sl->leaves_num);
596
597 for (size_t i = 0; i < sl->sln; ++i) {
598 slc = sl->sublevels[i];
599
600 if (slc) {
601 slc->sorted = sl->tosort;
602 slc->start_position = sl->start_position;
603 sl->start_position += slc->tosort_num;
604 push_ls(slc);
605 sl->sublevels[i] = NULL;
606 }
607 }
608
609 } else {
610 size_t n;
611
612 for (size_t i = 0; i < sl->sln; ++i) {
613
614 n = sl->sln - i - 1;
615 slc = sl->sublevels[n];
616
617 if (slc) {
618 slc->sorted = sl->tosort;
619 slc->start_position = sl->start_position;
620 sl->start_position += slc->tosort_num;
621 push_ls(slc);
622 sl->sublevels[n] = NULL;
623 }
624 }
625
626 memcpy(sl->tosort + sl->start_position, sl->leaves,
627 sl->leaves_num * sizeof(struct sort_list_item*));
628
629 sort_left_dec(sl->leaves_num);
630 }
631
632 #if defined(SORT_THREADS)
633 if (nthreads < 2) {
634 #endif
635 run_sort_cycle_st();
636 #if defined(SORT_THREADS)
637 } else {
638 size_t i;
639
640 for(i = 0; i < nthreads; ++i) {
641 pthread_attr_t attr;
642 pthread_t pth;
643
644 pthread_attr_init(&attr);
645 pthread_attr_setdetachstate(&attr, PTHREAD_DETACHED);
646
647 for (;;) {
648 int res = pthread_create(&pth, &attr,
649 sort_thread, NULL);
650 if (res >= 0)
651 break;
652 if (errno == EAGAIN) {
653 pthread_yield();
654 continue;
655 }
656 err(2, NULL);
657 }
658
659 pthread_attr_destroy(&attr);
660 }
661
662 for (i = 0; i < nthreads; ++i)
663 sem_wait(&mtsem);
664 }
665 #endif /* defined(SORT_THREADS) */
666 }
667
668 static void
run_sort(struct sort_list_item ** base,size_t nmemb)669 run_sort(struct sort_list_item **base, size_t nmemb)
670 {
671 struct sort_level *sl;
672
673 #if defined(SORT_THREADS)
674 size_t nthreads_save = nthreads;
675 if (nmemb < MT_SORT_THRESHOLD)
676 nthreads = 1;
677
678 if (nthreads > 1) {
679 pthread_mutexattr_t mattr;
680
681 pthread_mutexattr_init(&mattr);
682 pthread_mutexattr_settype(&mattr, PTHREAD_MUTEX_ADAPTIVE_NP);
683
684 pthread_mutex_init(&g_ls_mutex, &mattr);
685 pthread_cond_init(&g_ls_cond, NULL);
686
687 pthread_mutexattr_destroy(&mattr);
688
689 sem_init(&mtsem, 0, 0);
690
691 }
692 #endif
693
694 sl = sort_calloc(1, sizeof(struct sort_level));
695
696 sl->tosort = base;
697 sl->tosort_num = nmemb;
698 sl->tosort_sz = nmemb;
699
700 #if defined(SORT_THREADS)
701 sort_left = nmemb;
702 #endif
703
704 run_top_sort_level(sl);
705
706 free_sort_level(sl);
707
708 #if defined(SORT_THREADS)
709 if (nthreads > 1) {
710 sem_destroy(&mtsem);
711 pthread_mutex_destroy(&g_ls_mutex);
712 }
713 nthreads = nthreads_save;
714 #endif
715 }
716
717 void
rxsort(struct sort_list_item ** base,size_t nmemb)718 rxsort(struct sort_list_item **base, size_t nmemb)
719 {
720
721 run_sort(base, nmemb);
722 }
723