1 /*-
2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
3 *
4 * Copyright (C) 2012 Oleg Moskalenko <[email protected]>
5 * Copyright (C) 2012 Gabor Kovesdan <[email protected]>
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 __FBSDID("$FreeBSD$");
32
33 #include <errno.h>
34 #include <err.h>
35 #include <langinfo.h>
36 #include <math.h>
37 #if defined(SORT_THREADS)
38 #include <pthread.h>
39 #include <semaphore.h>
40 #endif
41 #include <stdlib.h>
42 #include <string.h>
43 #include <wchar.h>
44 #include <wctype.h>
45 #include <unistd.h>
46
47 #include "coll.h"
48 #include "radixsort.h"
49
50 #define DEFAULT_SORT_FUNC_RADIXSORT mergesort
51
52 #define TINY_NODE(sl) ((sl)->tosort_num < 65)
53 #define SMALL_NODE(sl) ((sl)->tosort_num < 5)
54
55 /* are we sorting in reverse order ? */
56 static bool reverse_sort;
57
58 /* sort sub-levels array size */
59 static const size_t slsz = 256 * sizeof(struct sort_level*);
60
61 /* one sort level structure */
62 struct sort_level
63 {
64 struct sort_level **sublevels;
65 struct sort_list_item **leaves;
66 struct sort_list_item **sorted;
67 struct sort_list_item **tosort;
68 size_t leaves_num;
69 size_t leaves_sz;
70 size_t level;
71 size_t real_sln;
72 size_t start_position;
73 size_t sln;
74 size_t tosort_num;
75 size_t tosort_sz;
76 };
77
78 /* stack of sort levels ready to be sorted */
79 struct level_stack {
80 struct level_stack *next;
81 struct sort_level *sl;
82 };
83
84 static struct level_stack *g_ls;
85
86 #if defined(SORT_THREADS)
87 /* stack guarding mutex */
88 static pthread_cond_t g_ls_cond;
89 static pthread_mutex_t g_ls_mutex;
90
91 /* counter: how many items are left */
92 static size_t sort_left;
93 /* guarding mutex */
94
95 /* semaphore to count threads */
96 static sem_t mtsem;
97
98 /*
99 * Decrement items counter
100 */
101 static inline void
sort_left_dec(size_t n)102 sort_left_dec(size_t n)
103 {
104 pthread_mutex_lock(&g_ls_mutex);
105 sort_left -= n;
106 if (sort_left == 0 && nthreads > 1)
107 pthread_cond_broadcast(&g_ls_cond);
108 pthread_mutex_unlock(&g_ls_mutex);
109 }
110
111 /*
112 * Do we have something to sort ?
113 *
114 * This routine does not need to be locked.
115 */
116 static inline bool
have_sort_left(void)117 have_sort_left(void)
118 {
119 bool ret;
120
121 ret = (sort_left > 0);
122
123 return (ret);
124 }
125
126 #else
127
128 #define sort_left_dec(n)
129
130 #endif /* SORT_THREADS */
131
132 static void
_push_ls(struct level_stack * ls)133 _push_ls(struct level_stack *ls)
134 {
135
136 ls->next = g_ls;
137 g_ls = ls;
138 }
139
140 /*
141 * Push sort level to the stack
142 */
143 static inline void
push_ls(struct sort_level * sl)144 push_ls(struct sort_level *sl)
145 {
146 struct level_stack *new_ls;
147
148 new_ls = sort_malloc(sizeof(struct level_stack));
149 new_ls->sl = sl;
150
151 #if defined(SORT_THREADS)
152 if (nthreads > 1) {
153 pthread_mutex_lock(&g_ls_mutex);
154 _push_ls(new_ls);
155 pthread_cond_signal(&g_ls_cond);
156 pthread_mutex_unlock(&g_ls_mutex);
157 } else
158 #endif
159 _push_ls(new_ls);
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 key_value *kv;
262 const struct bwstring *bws;
263
264 kv = get_key_from_keys_array(&sli->ka, 0);
265 bws = kv->k;
266
267 if ((BWSLEN(bws) > level))
268 return (unsigned char) BWS_GET(bws,level);
269 return (-1);
270 }
271
272 static void
place_item(struct sort_level * sl,size_t item)273 place_item(struct sort_level *sl, size_t item)
274 {
275 struct sort_list_item *sli;
276 int c;
277
278 sli = sl->tosort[item];
279 c = get_wc_index(sli, sl->level);
280
281 if (c == -1)
282 add_leaf(sl, sli);
283 else
284 add_to_sublevel(sl, sli, c);
285 }
286
287 static void
free_sort_level(struct sort_level * sl)288 free_sort_level(struct sort_level *sl)
289 {
290
291 if (sl) {
292 if (sl->leaves)
293 sort_free(sl->leaves);
294
295 if (sl->level > 0)
296 sort_free(sl->tosort);
297
298 if (sl->sublevels) {
299 struct sort_level *slc;
300 size_t sln;
301
302 sln = sl->sln;
303
304 for (size_t i = 0; i < sln; ++i) {
305 slc = sl->sublevels[i];
306 if (slc)
307 free_sort_level(slc);
308 }
309
310 sort_free(sl->sublevels);
311 }
312
313 sort_free(sl);
314 }
315 }
316
317 static void
run_sort_level_next(struct sort_level * sl)318 run_sort_level_next(struct sort_level *sl)
319 {
320 struct sort_level *slc;
321 size_t i, sln, tosort_num;
322
323 if (sl->sublevels) {
324 sort_free(sl->sublevels);
325 sl->sublevels = NULL;
326 }
327
328 switch (sl->tosort_num) {
329 case 0:
330 goto end;
331 case (1):
332 sl->sorted[sl->start_position] = sl->tosort[0];
333 sort_left_dec(1);
334 goto end;
335 case (2):
336 if (list_coll_offset(&(sl->tosort[0]), &(sl->tosort[1]),
337 sl->level) > 0) {
338 sl->sorted[sl->start_position++] = sl->tosort[1];
339 sl->sorted[sl->start_position] = sl->tosort[0];
340 } else {
341 sl->sorted[sl->start_position++] = sl->tosort[0];
342 sl->sorted[sl->start_position] = sl->tosort[1];
343 }
344 sort_left_dec(2);
345
346 goto end;
347 default:
348 if (TINY_NODE(sl) || (sl->level > 15)) {
349 listcoll_t func;
350
351 func = get_list_call_func(sl->level);
352
353 sl->leaves = sl->tosort;
354 sl->leaves_num = sl->tosort_num;
355 sl->leaves_sz = sl->leaves_num;
356 sl->leaves = sort_realloc(sl->leaves,
357 (sizeof(struct sort_list_item *) *
358 (sl->leaves_sz)));
359 sl->tosort = NULL;
360 sl->tosort_num = 0;
361 sl->tosort_sz = 0;
362 sl->sln = 0;
363 sl->real_sln = 0;
364 if (sort_opts_vals.sflag) {
365 if (mergesort(sl->leaves, sl->leaves_num,
366 sizeof(struct sort_list_item *),
367 (int(*)(const void *, const void *)) func) == -1)
368 /* NOTREACHED */
369 err(2, "Radix sort error 3");
370 } else
371 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
372 sizeof(struct sort_list_item *),
373 (int(*)(const void *, const void *)) func);
374
375 memcpy(sl->sorted + sl->start_position,
376 sl->leaves, sl->leaves_num *
377 sizeof(struct sort_list_item*));
378
379 sort_left_dec(sl->leaves_num);
380
381 goto end;
382 } else {
383 sl->tosort_sz = sl->tosort_num;
384 sl->tosort = sort_realloc(sl->tosort,
385 sizeof(struct sort_list_item*) * (sl->tosort_sz));
386 }
387 }
388
389 sl->sln = 256;
390 sl->sublevels = sort_malloc(slsz);
391 memset(sl->sublevels, 0, slsz);
392
393 sl->real_sln = 0;
394
395 tosort_num = sl->tosort_num;
396 for (i = 0; i < tosort_num; ++i)
397 place_item(sl, i);
398
399 sort_free(sl->tosort);
400 sl->tosort = NULL;
401 sl->tosort_num = 0;
402 sl->tosort_sz = 0;
403
404 if (sl->leaves_num > 1) {
405 if (keys_num > 1) {
406 if (sort_opts_vals.sflag) {
407 mergesort(sl->leaves, sl->leaves_num,
408 sizeof(struct sort_list_item *),
409 (int(*)(const void *, const void *)) list_coll);
410 } else {
411 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
412 sizeof(struct sort_list_item *),
413 (int(*)(const void *, const void *)) list_coll);
414 }
415 } else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) {
416 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
417 sizeof(struct sort_list_item *),
418 (int(*)(const void *, const void *)) list_coll_by_str_only);
419 }
420 }
421
422 sl->leaves_sz = sl->leaves_num;
423 sl->leaves = sort_realloc(sl->leaves, (sizeof(struct sort_list_item *) *
424 (sl->leaves_sz)));
425
426 if (!reverse_sort) {
427 memcpy(sl->sorted + sl->start_position, sl->leaves,
428 sl->leaves_num * sizeof(struct sort_list_item*));
429 sl->start_position += sl->leaves_num;
430 sort_left_dec(sl->leaves_num);
431
432 sort_free(sl->leaves);
433 sl->leaves = NULL;
434 sl->leaves_num = 0;
435 sl->leaves_sz = 0;
436
437 sln = sl->sln;
438
439 for (i = 0; i < sln; ++i) {
440 slc = sl->sublevels[i];
441
442 if (slc) {
443 slc->sorted = sl->sorted;
444 slc->start_position = sl->start_position;
445 sl->start_position += slc->tosort_num;
446 if (SMALL_NODE(slc))
447 run_sort_level_next(slc);
448 else
449 push_ls(slc);
450 sl->sublevels[i] = NULL;
451 }
452 }
453
454 } else {
455 size_t n;
456
457 sln = sl->sln;
458
459 for (i = 0; i < sln; ++i) {
460 n = sln - i - 1;
461 slc = sl->sublevels[n];
462
463 if (slc) {
464 slc->sorted = sl->sorted;
465 slc->start_position = sl->start_position;
466 sl->start_position += slc->tosort_num;
467 if (SMALL_NODE(slc))
468 run_sort_level_next(slc);
469 else
470 push_ls(slc);
471 sl->sublevels[n] = NULL;
472 }
473 }
474
475 memcpy(sl->sorted + sl->start_position, sl->leaves,
476 sl->leaves_num * sizeof(struct sort_list_item*));
477 sort_left_dec(sl->leaves_num);
478 }
479
480 end:
481 free_sort_level(sl);
482 }
483
484 /*
485 * Single-threaded sort cycle
486 */
487 static void
run_sort_cycle_st(void)488 run_sort_cycle_st(void)
489 {
490 struct sort_level *slc;
491
492 for (;;) {
493 slc = pop_ls_st();
494 if (slc == NULL) {
495 break;
496 }
497 run_sort_level_next(slc);
498 }
499 }
500
501 #if defined(SORT_THREADS)
502
503 /*
504 * Multi-threaded sort cycle
505 */
506 static void
run_sort_cycle_mt(void)507 run_sort_cycle_mt(void)
508 {
509 struct sort_level *slc;
510
511 for (;;) {
512 slc = pop_ls_mt();
513 if (slc == NULL)
514 break;
515 run_sort_level_next(slc);
516 }
517 }
518
519 /*
520 * Sort cycle thread (in multi-threaded mode)
521 */
522 static void*
sort_thread(void * arg)523 sort_thread(void* arg)
524 {
525 run_sort_cycle_mt();
526 sem_post(&mtsem);
527
528 return (arg);
529 }
530
531 #endif /* defined(SORT_THREADS) */
532
533 static void
run_top_sort_level(struct sort_level * sl)534 run_top_sort_level(struct sort_level *sl)
535 {
536 struct sort_level *slc;
537
538 reverse_sort = sort_opts_vals.kflag ? keys[0].sm.rflag :
539 default_sort_mods->rflag;
540
541 sl->start_position = 0;
542 sl->sln = 256;
543 sl->sublevels = sort_malloc(slsz);
544 memset(sl->sublevels, 0, slsz);
545
546 for (size_t i = 0; i < sl->tosort_num; ++i)
547 place_item(sl, i);
548
549 if (sl->leaves_num > 1) {
550 if (keys_num > 1) {
551 if (sort_opts_vals.sflag) {
552 mergesort(sl->leaves, sl->leaves_num,
553 sizeof(struct sort_list_item *),
554 (int(*)(const void *, const void *)) list_coll);
555 } else {
556 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
557 sizeof(struct sort_list_item *),
558 (int(*)(const void *, const void *)) list_coll);
559 }
560 } else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) {
561 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
562 sizeof(struct sort_list_item *),
563 (int(*)(const void *, const void *)) list_coll_by_str_only);
564 }
565 }
566
567 if (!reverse_sort) {
568 memcpy(sl->tosort + sl->start_position, sl->leaves,
569 sl->leaves_num * sizeof(struct sort_list_item*));
570 sl->start_position += sl->leaves_num;
571 sort_left_dec(sl->leaves_num);
572
573 for (size_t i = 0; i < sl->sln; ++i) {
574 slc = sl->sublevels[i];
575
576 if (slc) {
577 slc->sorted = sl->tosort;
578 slc->start_position = sl->start_position;
579 sl->start_position += slc->tosort_num;
580 push_ls(slc);
581 sl->sublevels[i] = NULL;
582 }
583 }
584
585 } else {
586 size_t n;
587
588 for (size_t i = 0; i < sl->sln; ++i) {
589
590 n = sl->sln - i - 1;
591 slc = sl->sublevels[n];
592
593 if (slc) {
594 slc->sorted = sl->tosort;
595 slc->start_position = sl->start_position;
596 sl->start_position += slc->tosort_num;
597 push_ls(slc);
598 sl->sublevels[n] = NULL;
599 }
600 }
601
602 memcpy(sl->tosort + sl->start_position, sl->leaves,
603 sl->leaves_num * sizeof(struct sort_list_item*));
604
605 sort_left_dec(sl->leaves_num);
606 }
607
608 #if defined(SORT_THREADS)
609 if (nthreads < 2) {
610 #endif
611 run_sort_cycle_st();
612 #if defined(SORT_THREADS)
613 } else {
614 size_t i;
615
616 for(i = 0; i < nthreads; ++i) {
617 pthread_attr_t attr;
618 pthread_t pth;
619
620 pthread_attr_init(&attr);
621 pthread_attr_setdetachstate(&attr, PTHREAD_DETACHED);
622
623 for (;;) {
624 int res = pthread_create(&pth, &attr,
625 sort_thread, NULL);
626 if (res >= 0)
627 break;
628 if (errno == EAGAIN) {
629 pthread_yield();
630 continue;
631 }
632 err(2, NULL);
633 }
634
635 pthread_attr_destroy(&attr);
636 }
637
638 for (i = 0; i < nthreads; ++i)
639 sem_wait(&mtsem);
640 }
641 #endif /* defined(SORT_THREADS) */
642 }
643
644 static void
run_sort(struct sort_list_item ** base,size_t nmemb)645 run_sort(struct sort_list_item **base, size_t nmemb)
646 {
647 struct sort_level *sl;
648
649 #if defined(SORT_THREADS)
650 size_t nthreads_save = nthreads;
651 if (nmemb < MT_SORT_THRESHOLD)
652 nthreads = 1;
653
654 if (nthreads > 1) {
655 pthread_mutexattr_t mattr;
656
657 pthread_mutexattr_init(&mattr);
658 pthread_mutexattr_settype(&mattr, PTHREAD_MUTEX_ADAPTIVE_NP);
659
660 pthread_mutex_init(&g_ls_mutex, &mattr);
661 pthread_cond_init(&g_ls_cond, NULL);
662
663 pthread_mutexattr_destroy(&mattr);
664
665 sem_init(&mtsem, 0, 0);
666
667 }
668 #endif
669
670 sl = sort_malloc(sizeof(struct sort_level));
671 memset(sl, 0, sizeof(struct sort_level));
672
673 sl->tosort = base;
674 sl->tosort_num = nmemb;
675 sl->tosort_sz = nmemb;
676
677 #if defined(SORT_THREADS)
678 sort_left = nmemb;
679 #endif
680
681 run_top_sort_level(sl);
682
683 free_sort_level(sl);
684
685 #if defined(SORT_THREADS)
686 if (nthreads > 1) {
687 sem_destroy(&mtsem);
688 pthread_mutex_destroy(&g_ls_mutex);
689 }
690 nthreads = nthreads_save;
691 #endif
692 }
693
694 void
rxsort(struct sort_list_item ** base,size_t nmemb)695 rxsort(struct sort_list_item **base, size_t nmemb)
696 {
697
698 run_sort(base, nmemb);
699 }
700