2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
4 * Copyright (C) 2012 Oleg Moskalenko <mom040267@gmail.com>
5 * Copyright (C) 2012 Gabor Kovesdan <gabor@FreeBSD.org>
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
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.
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
30 #include <sys/cdefs.h>
31 __FBSDID("$FreeBSD$");
37 #if defined(SORT_THREADS)
39 #include <semaphore.h>
48 #include "radixsort.h"
50 #define DEFAULT_SORT_FUNC_RADIXSORT mergesort
52 #define TINY_NODE(sl) ((sl)->tosort_num < 65)
53 #define SMALL_NODE(sl) ((sl)->tosort_num < 5)
55 /* are we sorting in reverse order ? */
56 static bool reverse_sort;
58 /* sort sub-levels array size */
59 static const size_t slsz = 256 * sizeof(struct sort_level*);
61 /* one sort level structure */
64 struct sort_level **sublevels;
65 struct sort_list_item **leaves;
66 struct sort_list_item **sorted;
67 struct sort_list_item **tosort;
72 size_t start_position;
78 /* stack of sort levels ready to be sorted */
80 struct level_stack *next;
81 struct sort_level *sl;
84 static struct level_stack *g_ls;
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;
91 /* counter: how many items are left */
92 static size_t sort_left;
95 /* semaphore to count threads */
99 * Decrement items counter
102 sort_left_dec(size_t n)
104 pthread_mutex_lock(&g_ls_mutex);
106 if (sort_left == 0 && nthreads > 1)
107 pthread_cond_broadcast(&g_ls_cond);
108 pthread_mutex_unlock(&g_ls_mutex);
112 * Do we have something to sort ?
114 * This routine does not need to be locked.
121 ret = (sort_left > 0);
128 #define sort_left_dec(n)
130 #endif /* SORT_THREADS */
133 _push_ls(struct level_stack *ls)
141 * Push sort level to the stack
144 push_ls(struct sort_level *sl)
146 struct level_stack *new_ls;
148 new_ls = sort_malloc(sizeof(struct level_stack));
151 #if defined(SORT_THREADS)
153 pthread_mutex_lock(&g_ls_mutex);
155 pthread_cond_signal(&g_ls_cond);
156 pthread_mutex_unlock(&g_ls_mutex);
163 * Pop sort level from the stack (single-threaded style)
165 static inline struct sort_level*
168 struct sort_level *sl;
171 struct level_stack *saved_ls;
183 #if defined(SORT_THREADS)
186 * Pop sort level from the stack (multi-threaded style)
188 static inline struct sort_level*
191 struct level_stack *saved_ls;
192 struct sort_level *sl;
194 pthread_mutex_lock(&g_ls_mutex);
206 if (have_sort_left() == 0)
208 pthread_cond_wait(&g_ls_cond, &g_ls_mutex);
211 pthread_mutex_unlock(&g_ls_mutex);
218 #endif /* defined(SORT_THREADS) */
221 add_to_sublevel(struct sort_level *sl, struct sort_list_item *item, size_t indx)
223 struct sort_level *ssl;
225 ssl = sl->sublevels[indx];
228 ssl = sort_malloc(sizeof(struct sort_level));
229 memset(ssl, 0, sizeof(struct sort_level));
231 ssl->level = sl->level + 1;
232 sl->sublevels[indx] = ssl;
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));
243 ssl->tosort[ssl->tosort_num - 1] = item;
247 add_leaf(struct sort_level *sl, struct sort_list_item *item)
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)));
255 sl->leaves[sl->leaves_num - 1] = item;
259 get_wc_index(struct sort_list_item *sli, size_t level)
261 const struct key_value *kv;
262 const struct bwstring *bws;
264 kv = get_key_from_keys_array(&sli->ka, 0);
267 if ((BWSLEN(bws) > level))
268 return (unsigned char) BWS_GET(bws,level);
273 place_item(struct sort_level *sl, size_t item)
275 struct sort_list_item *sli;
278 sli = sl->tosort[item];
279 c = get_wc_index(sli, sl->level);
284 add_to_sublevel(sl, sli, c);
288 free_sort_level(struct sort_level *sl)
293 sort_free(sl->leaves);
296 sort_free(sl->tosort);
299 struct sort_level *slc;
304 for (size_t i = 0; i < sln; ++i) {
305 slc = sl->sublevels[i];
307 free_sort_level(slc);
310 sort_free(sl->sublevels);
318 run_sort_level_next(struct sort_level *sl)
320 struct sort_level *slc;
321 size_t i, sln, tosort_num;
324 sort_free(sl->sublevels);
325 sl->sublevels = NULL;
328 switch (sl->tosort_num) {
332 sl->sorted[sl->start_position] = sl->tosort[0];
336 if (list_coll_offset(&(sl->tosort[0]), &(sl->tosort[1]),
338 sl->sorted[sl->start_position++] = sl->tosort[1];
339 sl->sorted[sl->start_position] = sl->tosort[0];
341 sl->sorted[sl->start_position++] = sl->tosort[0];
342 sl->sorted[sl->start_position] = sl->tosort[1];
348 if (TINY_NODE(sl) || (sl->level > 15)) {
351 func = get_list_call_func(sl->level);
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 *) *
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)
369 err(2, "Radix sort error 3");
371 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
372 sizeof(struct sort_list_item *),
373 (int(*)(const void *, const void *)) func);
375 memcpy(sl->sorted + sl->start_position,
376 sl->leaves, sl->leaves_num *
377 sizeof(struct sort_list_item*));
379 sort_left_dec(sl->leaves_num);
383 sl->tosort_sz = sl->tosort_num;
384 sl->tosort = sort_realloc(sl->tosort,
385 sizeof(struct sort_list_item*) * (sl->tosort_sz));
390 sl->sublevels = sort_malloc(slsz);
391 memset(sl->sublevels, 0, slsz);
395 tosort_num = sl->tosort_num;
396 for (i = 0; i < tosort_num; ++i)
399 sort_free(sl->tosort);
404 if (sl->leaves_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);
411 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
412 sizeof(struct sort_list_item *),
413 (int(*)(const void *, const void *)) list_coll);
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);
422 sl->leaves_sz = sl->leaves_num;
423 sl->leaves = sort_realloc(sl->leaves, (sizeof(struct sort_list_item *) *
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);
432 sort_free(sl->leaves);
439 for (i = 0; i < sln; ++i) {
440 slc = sl->sublevels[i];
443 slc->sorted = sl->sorted;
444 slc->start_position = sl->start_position;
445 sl->start_position += slc->tosort_num;
447 run_sort_level_next(slc);
450 sl->sublevels[i] = NULL;
459 for (i = 0; i < sln; ++i) {
461 slc = sl->sublevels[n];
464 slc->sorted = sl->sorted;
465 slc->start_position = sl->start_position;
466 sl->start_position += slc->tosort_num;
468 run_sort_level_next(slc);
471 sl->sublevels[n] = NULL;
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);
485 * Single-threaded sort cycle
488 run_sort_cycle_st(void)
490 struct sort_level *slc;
497 run_sort_level_next(slc);
501 #if defined(SORT_THREADS)
504 * Multi-threaded sort cycle
507 run_sort_cycle_mt(void)
509 struct sort_level *slc;
515 run_sort_level_next(slc);
520 * Sort cycle thread (in multi-threaded mode)
523 sort_thread(void* arg)
531 #endif /* defined(SORT_THREADS) */
534 run_top_sort_level(struct sort_level *sl)
536 struct sort_level *slc;
538 reverse_sort = sort_opts_vals.kflag ? keys[0].sm.rflag :
539 default_sort_mods->rflag;
541 sl->start_position = 0;
543 sl->sublevels = sort_malloc(slsz);
544 memset(sl->sublevels, 0, slsz);
546 for (size_t i = 0; i < sl->tosort_num; ++i)
549 if (sl->leaves_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);
556 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
557 sizeof(struct sort_list_item *),
558 (int(*)(const void *, const void *)) list_coll);
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);
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);
573 for (size_t i = 0; i < sl->sln; ++i) {
574 slc = sl->sublevels[i];
577 slc->sorted = sl->tosort;
578 slc->start_position = sl->start_position;
579 sl->start_position += slc->tosort_num;
581 sl->sublevels[i] = NULL;
588 for (size_t i = 0; i < sl->sln; ++i) {
591 slc = sl->sublevels[n];
594 slc->sorted = sl->tosort;
595 slc->start_position = sl->start_position;
596 sl->start_position += slc->tosort_num;
598 sl->sublevels[n] = NULL;
602 memcpy(sl->tosort + sl->start_position, sl->leaves,
603 sl->leaves_num * sizeof(struct sort_list_item*));
605 sort_left_dec(sl->leaves_num);
608 #if defined(SORT_THREADS)
612 #if defined(SORT_THREADS)
616 for(i = 0; i < nthreads; ++i) {
620 pthread_attr_init(&attr);
621 pthread_attr_setdetachstate(&attr, PTHREAD_DETACHED);
624 int res = pthread_create(&pth, &attr,
628 if (errno == EAGAIN) {
635 pthread_attr_destroy(&attr);
638 for (i = 0; i < nthreads; ++i)
641 #endif /* defined(SORT_THREADS) */
645 run_sort(struct sort_list_item **base, size_t nmemb)
647 struct sort_level *sl;
649 #if defined(SORT_THREADS)
650 size_t nthreads_save = nthreads;
651 if (nmemb < MT_SORT_THRESHOLD)
655 pthread_mutexattr_t mattr;
657 pthread_mutexattr_init(&mattr);
658 pthread_mutexattr_settype(&mattr, PTHREAD_MUTEX_ADAPTIVE_NP);
660 pthread_mutex_init(&g_ls_mutex, &mattr);
661 pthread_cond_init(&g_ls_cond, NULL);
663 pthread_mutexattr_destroy(&mattr);
665 sem_init(&mtsem, 0, 0);
670 sl = sort_malloc(sizeof(struct sort_level));
671 memset(sl, 0, sizeof(struct sort_level));
674 sl->tosort_num = nmemb;
675 sl->tosort_sz = nmemb;
677 #if defined(SORT_THREADS)
681 run_top_sort_level(sl);
685 #if defined(SORT_THREADS)
688 pthread_mutex_destroy(&g_ls_mutex);
690 nthreads = nthreads_save;
695 rxsort(struct sort_list_item **base, size_t nmemb)
698 run_sort(base, nmemb);