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
28 #include <sys/cdefs.h>
29 __FBSDID("$FreeBSD$");
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
sort_left_dec(size_t n)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
have_sort_left(void)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
push_ls(struct sort_level * sl)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*
pop_ls_st(void)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*
pop_ls_mt(void)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
add_to_sublevel(struct sort_level * sl,struct sort_list_item * item,size_t indx)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
add_leaf(struct sort_level * sl,struct sort_list_item * item)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
get_wc_index(struct sort_list_item * sli,size_t level)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
place_item(struct sort_level * sl,size_t item)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
free_sort_level(struct sort_level * sl)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
run_sort_level_next(struct sort_level * sl)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
run_sort_cycle_st(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
run_sort_cycle_mt(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*
sort_thread(void * arg)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
run_top_sort_level(struct sort_level * sl)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
run_sort(struct sort_list_item ** base,size_t nmemb)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_ADAPTIVE_NP);
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
rxsort(struct sort_list_item ** base,size_t nmemb)687 rxsort(struct sort_list_item **base, size_t nmemb)
688 {
689
690 run_sort(base, nmemb);
691 }
692