2 * Copyright (C) 2012 Oleg Moskalenko <mom040267@gmail.com>
3 * Copyright (C) 2012 Gabor Kovesdan <gabor@FreeBSD.org>
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
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.
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
28 #include <sys/cdefs.h>
29 __FBSDID("$FreeBSD$");
35 #if defined(SORT_THREADS)
37 #include <semaphore.h>
46 #include "radixsort.h"
48 #define DEFAULT_SORT_FUNC_RADIXSORT mergesort
50 #define TINY_NODE(sl) ((sl)->tosort_num < 65)
51 #define SMALL_NODE(sl) ((sl)->tosort_num < 5)
53 /* are we sorting in reverse order ? */
54 static bool reverse_sort;
56 /* sort sub-levels array size */
57 static const size_t slsz = 256 * sizeof(struct sort_level*);
59 /* one sort level structure */
62 struct sort_level **sublevels;
63 struct sort_list_item **leaves;
64 struct sort_list_item **sorted;
65 struct sort_list_item **tosort;
70 size_t start_position;
76 /* stack of sort levels ready to be sorted */
78 struct level_stack *next;
79 struct sort_level *sl;
82 static struct level_stack *g_ls;
84 #if defined(SORT_THREADS)
85 /* stack guarding mutex */
86 static pthread_mutex_t g_ls_mutex;
88 /* counter: how many items are left */
89 static size_t sort_left;
91 static pthread_mutex_t sort_left_mutex;
93 /* semaphore to count threads */
97 * Decrement items counter
100 sort_left_dec(size_t n)
103 pthread_mutex_lock(&sort_left_mutex);
105 pthread_mutex_unlock(&sort_left_mutex);
109 * Do we have something to sort ?
116 pthread_mutex_lock(&sort_left_mutex);
117 ret = (sort_left > 0);
118 pthread_mutex_unlock(&sort_left_mutex);
124 #define sort_left_dec(n)
126 #endif /* SORT_THREADS */
129 * Push sort level to the stack
132 push_ls(struct sort_level *sl)
134 struct level_stack *new_ls;
136 new_ls = sort_malloc(sizeof(struct level_stack));
139 #if defined(SORT_THREADS)
141 pthread_mutex_lock(&g_ls_mutex);
147 #if defined(SORT_THREADS)
149 pthread_mutex_unlock(&g_ls_mutex);
154 * Pop sort level from the stack (single-threaded style)
156 static inline struct sort_level*
159 struct sort_level *sl;
162 struct level_stack *saved_ls;
174 #if defined(SORT_THREADS)
177 * Pop sort level from the stack (multi-threaded style)
179 static inline struct sort_level*
182 struct level_stack *saved_ls;
183 struct sort_level *sl;
185 pthread_mutex_lock(&g_ls_mutex);
196 pthread_mutex_unlock(&g_ls_mutex);
203 #endif /* defined(SORT_THREADS) */
206 add_to_sublevel(struct sort_level *sl, struct sort_list_item *item, size_t indx)
208 struct sort_level *ssl;
210 ssl = sl->sublevels[indx];
213 ssl = sort_malloc(sizeof(struct sort_level));
214 memset(ssl, 0, sizeof(struct sort_level));
216 ssl->level = sl->level + 1;
217 sl->sublevels[indx] = ssl;
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));
228 ssl->tosort[ssl->tosort_num - 1] = item;
232 add_leaf(struct sort_level *sl, struct sort_list_item *item)
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)));
240 sl->leaves[sl->leaves_num - 1] = item;
244 get_wc_index(struct sort_list_item *sli, size_t level)
246 const struct key_value *kv;
247 const struct bwstring *bws;
249 kv = get_key_from_keys_array(&sli->ka, 0);
252 if ((BWSLEN(bws) > level))
253 return (unsigned char) BWS_GET(bws,level);
258 place_item(struct sort_level *sl, size_t item)
260 struct sort_list_item *sli;
263 sli = sl->tosort[item];
264 c = get_wc_index(sli, sl->level);
269 add_to_sublevel(sl, sli, c);
273 free_sort_level(struct sort_level *sl)
278 sort_free(sl->leaves);
281 sort_free(sl->tosort);
284 struct sort_level *slc;
289 for (size_t i = 0; i < sln; ++i) {
290 slc = sl->sublevels[i];
292 free_sort_level(slc);
295 sort_free(sl->sublevels);
303 run_sort_level_next(struct sort_level *sl)
305 struct sort_level *slc;
306 size_t i, sln, tosort_num;
309 sort_free(sl->sublevels);
310 sl->sublevels = NULL;
313 switch (sl->tosort_num) {
317 sl->sorted[sl->start_position] = sl->tosort[0];
321 if (list_coll_offset(&(sl->tosort[0]), &(sl->tosort[1]),
323 sl->sorted[sl->start_position++] = sl->tosort[1];
324 sl->sorted[sl->start_position] = sl->tosort[0];
326 sl->sorted[sl->start_position++] = sl->tosort[0];
327 sl->sorted[sl->start_position] = sl->tosort[1];
333 if (TINY_NODE(sl) || (sl->level > 15)) {
336 func = get_list_call_func(sl->level);
338 sl->leaves = sl->tosort;
339 sl->leaves_num = sl->tosort_num;
340 sl->leaves_sz = sl->leaves_num;
341 sl->leaves = sort_realloc(sl->leaves,
342 (sizeof(struct sort_list_item *) *
349 if (sort_opts_vals.sflag) {
350 if (mergesort(sl->leaves, sl->leaves_num,
351 sizeof(struct sort_list_item *),
352 (int(*)(const void *, const void *)) func) == -1)
354 err(2, "Radix sort error 3");
356 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
357 sizeof(struct sort_list_item *),
358 (int(*)(const void *, const void *)) func);
360 memcpy(sl->sorted + sl->start_position,
361 sl->leaves, sl->leaves_num *
362 sizeof(struct sort_list_item*));
364 sort_left_dec(sl->leaves_num);
368 sl->tosort_sz = sl->tosort_num;
369 sl->tosort = sort_realloc(sl->tosort,
370 sizeof(struct sort_list_item*) * (sl->tosort_sz));
375 sl->sublevels = sort_malloc(slsz);
376 memset(sl->sublevels, 0, slsz);
380 tosort_num = sl->tosort_num;
381 for (i = 0; i < tosort_num; ++i)
384 sort_free(sl->tosort);
389 if (sl->leaves_num > 1) {
391 if (sort_opts_vals.sflag) {
392 mergesort(sl->leaves, sl->leaves_num,
393 sizeof(struct sort_list_item *),
394 (int(*)(const void *, const void *)) list_coll);
396 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
397 sizeof(struct sort_list_item *),
398 (int(*)(const void *, const void *)) list_coll);
400 } else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) {
401 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
402 sizeof(struct sort_list_item *),
403 (int(*)(const void *, const void *)) list_coll_by_str_only);
407 sl->leaves_sz = sl->leaves_num;
408 sl->leaves = sort_realloc(sl->leaves, (sizeof(struct sort_list_item *) *
412 memcpy(sl->sorted + sl->start_position, sl->leaves,
413 sl->leaves_num * sizeof(struct sort_list_item*));
414 sl->start_position += sl->leaves_num;
415 sort_left_dec(sl->leaves_num);
417 sort_free(sl->leaves);
424 for (i = 0; i < sln; ++i) {
425 slc = sl->sublevels[i];
428 slc->sorted = sl->sorted;
429 slc->start_position = sl->start_position;
430 sl->start_position += slc->tosort_num;
432 run_sort_level_next(slc);
435 sl->sublevels[i] = NULL;
444 for (i = 0; i < sln; ++i) {
446 slc = sl->sublevels[n];
449 slc->sorted = sl->sorted;
450 slc->start_position = sl->start_position;
451 sl->start_position += slc->tosort_num;
453 run_sort_level_next(slc);
456 sl->sublevels[n] = NULL;
460 memcpy(sl->sorted + sl->start_position, sl->leaves,
461 sl->leaves_num * sizeof(struct sort_list_item*));
462 sort_left_dec(sl->leaves_num);
470 * Single-threaded sort cycle
473 run_sort_cycle_st(void)
475 struct sort_level *slc;
482 run_sort_level_next(slc);
486 #if defined(SORT_THREADS)
489 * Multi-threaded sort cycle
492 run_sort_cycle_mt(void)
494 struct sort_level *slc;
499 if (have_sort_left()) {
505 run_sort_level_next(slc);
510 * Sort cycle thread (in multi-threaded mode)
513 sort_thread(void* arg)
523 #endif /* defined(SORT_THREADS) */
526 run_top_sort_level(struct sort_level *sl)
528 struct sort_level *slc;
530 reverse_sort = sort_opts_vals.kflag ? keys[0].sm.rflag :
531 default_sort_mods->rflag;
533 sl->start_position = 0;
535 sl->sublevels = sort_malloc(slsz);
536 memset(sl->sublevels, 0, slsz);
538 for (size_t i = 0; i < sl->tosort_num; ++i)
541 if (sl->leaves_num > 1) {
543 if (sort_opts_vals.sflag) {
544 mergesort(sl->leaves, sl->leaves_num,
545 sizeof(struct sort_list_item *),
546 (int(*)(const void *, const void *)) list_coll);
548 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
549 sizeof(struct sort_list_item *),
550 (int(*)(const void *, const void *)) list_coll);
552 } else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) {
553 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
554 sizeof(struct sort_list_item *),
555 (int(*)(const void *, const void *)) list_coll_by_str_only);
560 memcpy(sl->tosort + sl->start_position, sl->leaves,
561 sl->leaves_num * sizeof(struct sort_list_item*));
562 sl->start_position += sl->leaves_num;
563 sort_left_dec(sl->leaves_num);
565 for (size_t i = 0; i < sl->sln; ++i) {
566 slc = sl->sublevels[i];
569 slc->sorted = sl->tosort;
570 slc->start_position = sl->start_position;
571 sl->start_position += slc->tosort_num;
573 sl->sublevels[i] = NULL;
580 for (size_t i = 0; i < sl->sln; ++i) {
583 slc = sl->sublevels[n];
586 slc->sorted = sl->tosort;
587 slc->start_position = sl->start_position;
588 sl->start_position += slc->tosort_num;
590 sl->sublevels[n] = NULL;
594 memcpy(sl->tosort + sl->start_position, sl->leaves,
595 sl->leaves_num * sizeof(struct sort_list_item*));
597 sort_left_dec(sl->leaves_num);
600 #if defined(SORT_THREADS)
604 #if defined(SORT_THREADS)
608 for(i = 0; i < nthreads; ++i) {
612 pthread_attr_init(&attr);
613 pthread_attr_setdetachstate(&attr,
617 int res = pthread_create(&pth, &attr,
621 if (errno == EAGAIN) {
628 pthread_attr_destroy(&attr);
631 for(i = 0; i < nthreads; ++i)
634 #endif /* defined(SORT_THREADS) */
638 run_sort(struct sort_list_item **base, size_t nmemb)
640 struct sort_level *sl;
642 #if defined(SORT_THREADS)
643 size_t nthreads_save = nthreads;
644 if (nmemb < MT_SORT_THRESHOLD)
648 pthread_mutexattr_t mattr;
650 pthread_mutexattr_init(&mattr);
651 pthread_mutexattr_settype(&mattr, PTHREAD_MUTEX_ADAPTIVE_NP);
653 pthread_mutex_init(&g_ls_mutex, &mattr);
654 pthread_mutex_init(&sort_left_mutex, &mattr);
656 pthread_mutexattr_destroy(&mattr);
658 sem_init(&mtsem, 0, 0);
663 sl = sort_malloc(sizeof(struct sort_level));
664 memset(sl, 0, sizeof(struct sort_level));
667 sl->tosort_num = nmemb;
668 sl->tosort_sz = nmemb;
670 #if defined(SORT_THREADS)
674 run_top_sort_level(sl);
678 #if defined(SORT_THREADS)
681 pthread_mutex_destroy(&g_ls_mutex);
682 pthread_mutex_destroy(&sort_left_mutex);
684 nthreads = nthreads_save;
689 rxsort(struct sort_list_item **base, size_t nmemb)
692 run_sort(base, nmemb);