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_calloc(1, sizeof(struct sort_level));
230 ssl->level = sl->level + 1;
231 sl->sublevels[indx] = ssl;
236 if (++(ssl->tosort_num) > ssl->tosort_sz) {
237 ssl->tosort_sz = ssl->tosort_num + 128;
238 ssl->tosort = sort_realloc(ssl->tosort,
239 sizeof(struct sort_list_item*) * (ssl->tosort_sz));
242 ssl->tosort[ssl->tosort_num - 1] = item;
246 add_leaf(struct sort_level *sl, struct sort_list_item *item)
249 if (++(sl->leaves_num) > sl->leaves_sz) {
250 sl->leaves_sz = sl->leaves_num + 128;
251 sl->leaves = sort_realloc(sl->leaves,
252 (sizeof(struct sort_list_item*) * (sl->leaves_sz)));
254 sl->leaves[sl->leaves_num - 1] = item;
258 get_wc_index(struct sort_list_item *sli, size_t level)
260 const size_t wcfact = (mb_cur_max == 1) ? 1 : sizeof(wchar_t);
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) * wcfact > level)) {
271 * Sort wchar strings a byte at a time, rather than a single
272 * byte from each wchar.
274 res = (wchar_t)BWS_GET(bws, level / wcfact);
275 /* Sort most-significant byte first. */
276 if (level % wcfact < wcfact - 1)
277 res = (res >> (8 * (wcfact - 1 - (level % wcfact))));
286 place_item(struct sort_level *sl, size_t item)
288 struct sort_list_item *sli;
291 sli = sl->tosort[item];
292 c = get_wc_index(sli, sl->level);
297 add_to_sublevel(sl, sli, c);
301 free_sort_level(struct sort_level *sl)
306 sort_free(sl->leaves);
309 sort_free(sl->tosort);
312 struct sort_level *slc;
317 for (size_t i = 0; i < sln; ++i) {
318 slc = sl->sublevels[i];
320 free_sort_level(slc);
323 sort_free(sl->sublevels);
331 run_sort_level_next(struct sort_level *sl)
333 const size_t wcfact = (mb_cur_max == 1) ? 1 : sizeof(wchar_t);
334 struct sort_level *slc;
335 size_t i, sln, tosort_num;
338 sort_free(sl->sublevels);
339 sl->sublevels = NULL;
342 switch (sl->tosort_num) {
346 sl->sorted[sl->start_position] = sl->tosort[0];
351 * Radixsort only processes a single byte at a time. In wchar
352 * mode, this can be a subset of the length of a character.
353 * list_coll_offset() offset is in units of wchar, not bytes.
354 * So to calculate the offset, we must divide by
355 * sizeof(wchar_t) and round down to the index of the first
356 * character this level references.
358 if (list_coll_offset(&(sl->tosort[0]), &(sl->tosort[1]),
359 sl->level / wcfact) > 0) {
360 sl->sorted[sl->start_position++] = sl->tosort[1];
361 sl->sorted[sl->start_position] = sl->tosort[0];
363 sl->sorted[sl->start_position++] = sl->tosort[0];
364 sl->sorted[sl->start_position] = sl->tosort[1];
370 if (TINY_NODE(sl) || (sl->level > 15)) {
374 * Collate comparison offset is in units of
375 * character-width, so we must divide the level (bytes)
376 * by operating character width (wchar_t or char). See
377 * longer comment above.
379 func = get_list_call_func(sl->level / wcfact);
381 sl->leaves = sl->tosort;
382 sl->leaves_num = sl->tosort_num;
383 sl->leaves_sz = sl->leaves_num;
384 sl->leaves = sort_realloc(sl->leaves,
385 (sizeof(struct sort_list_item *) *
392 if (sort_opts_vals.sflag) {
393 if (mergesort(sl->leaves, sl->leaves_num,
394 sizeof(struct sort_list_item *),
395 (int(*)(const void *, const void *)) func) == -1)
397 err(2, "Radix sort error 3");
399 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
400 sizeof(struct sort_list_item *),
401 (int(*)(const void *, const void *)) func);
403 memcpy(sl->sorted + sl->start_position,
404 sl->leaves, sl->leaves_num *
405 sizeof(struct sort_list_item*));
407 sort_left_dec(sl->leaves_num);
411 sl->tosort_sz = sl->tosort_num;
412 sl->tosort = sort_realloc(sl->tosort,
413 sizeof(struct sort_list_item*) * (sl->tosort_sz));
418 sl->sublevels = sort_calloc(1, slsz);
422 tosort_num = sl->tosort_num;
423 for (i = 0; i < tosort_num; ++i)
426 sort_free(sl->tosort);
431 if (sl->leaves_num > 1) {
433 if (sort_opts_vals.sflag) {
434 mergesort(sl->leaves, sl->leaves_num,
435 sizeof(struct sort_list_item *),
436 (int(*)(const void *, const void *)) list_coll);
438 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
439 sizeof(struct sort_list_item *),
440 (int(*)(const void *, const void *)) list_coll);
442 } else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) {
443 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
444 sizeof(struct sort_list_item *),
445 (int(*)(const void *, const void *)) list_coll_by_str_only);
449 sl->leaves_sz = sl->leaves_num;
450 sl->leaves = sort_realloc(sl->leaves, (sizeof(struct sort_list_item *) *
454 memcpy(sl->sorted + sl->start_position, sl->leaves,
455 sl->leaves_num * sizeof(struct sort_list_item*));
456 sl->start_position += sl->leaves_num;
457 sort_left_dec(sl->leaves_num);
459 sort_free(sl->leaves);
466 for (i = 0; i < sln; ++i) {
467 slc = sl->sublevels[i];
470 slc->sorted = sl->sorted;
471 slc->start_position = sl->start_position;
472 sl->start_position += slc->tosort_num;
474 run_sort_level_next(slc);
477 sl->sublevels[i] = NULL;
486 for (i = 0; i < sln; ++i) {
488 slc = sl->sublevels[n];
491 slc->sorted = sl->sorted;
492 slc->start_position = sl->start_position;
493 sl->start_position += slc->tosort_num;
495 run_sort_level_next(slc);
498 sl->sublevels[n] = NULL;
502 memcpy(sl->sorted + sl->start_position, sl->leaves,
503 sl->leaves_num * sizeof(struct sort_list_item*));
504 sort_left_dec(sl->leaves_num);
512 * Single-threaded sort cycle
515 run_sort_cycle_st(void)
517 struct sort_level *slc;
524 run_sort_level_next(slc);
528 #if defined(SORT_THREADS)
531 * Multi-threaded sort cycle
534 run_sort_cycle_mt(void)
536 struct sort_level *slc;
542 run_sort_level_next(slc);
547 * Sort cycle thread (in multi-threaded mode)
550 sort_thread(void* arg)
558 #endif /* defined(SORT_THREADS) */
561 run_top_sort_level(struct sort_level *sl)
563 struct sort_level *slc;
565 reverse_sort = sort_opts_vals.kflag ? keys[0].sm.rflag :
566 default_sort_mods->rflag;
568 sl->start_position = 0;
570 sl->sublevels = sort_calloc(1, slsz);
572 for (size_t i = 0; i < sl->tosort_num; ++i)
575 if (sl->leaves_num > 1) {
577 if (sort_opts_vals.sflag) {
578 mergesort(sl->leaves, sl->leaves_num,
579 sizeof(struct sort_list_item *),
580 (int(*)(const void *, const void *)) list_coll);
582 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
583 sizeof(struct sort_list_item *),
584 (int(*)(const void *, const void *)) list_coll);
586 } else if (!sort_opts_vals.sflag && sort_opts_vals.complex_sort) {
587 DEFAULT_SORT_FUNC_RADIXSORT(sl->leaves, sl->leaves_num,
588 sizeof(struct sort_list_item *),
589 (int(*)(const void *, const void *)) list_coll_by_str_only);
594 memcpy(sl->tosort + sl->start_position, sl->leaves,
595 sl->leaves_num * sizeof(struct sort_list_item*));
596 sl->start_position += sl->leaves_num;
597 sort_left_dec(sl->leaves_num);
599 for (size_t i = 0; i < sl->sln; ++i) {
600 slc = sl->sublevels[i];
603 slc->sorted = sl->tosort;
604 slc->start_position = sl->start_position;
605 sl->start_position += slc->tosort_num;
607 sl->sublevels[i] = NULL;
614 for (size_t i = 0; i < sl->sln; ++i) {
617 slc = sl->sublevels[n];
620 slc->sorted = sl->tosort;
621 slc->start_position = sl->start_position;
622 sl->start_position += slc->tosort_num;
624 sl->sublevels[n] = NULL;
628 memcpy(sl->tosort + sl->start_position, sl->leaves,
629 sl->leaves_num * sizeof(struct sort_list_item*));
631 sort_left_dec(sl->leaves_num);
634 #if defined(SORT_THREADS)
638 #if defined(SORT_THREADS)
642 for(i = 0; i < nthreads; ++i) {
646 pthread_attr_init(&attr);
647 pthread_attr_setdetachstate(&attr, PTHREAD_DETACHED);
650 int res = pthread_create(&pth, &attr,
654 if (errno == EAGAIN) {
661 pthread_attr_destroy(&attr);
664 for (i = 0; i < nthreads; ++i)
667 #endif /* defined(SORT_THREADS) */
671 run_sort(struct sort_list_item **base, size_t nmemb)
673 struct sort_level *sl;
675 #if defined(SORT_THREADS)
676 size_t nthreads_save = nthreads;
677 if (nmemb < MT_SORT_THRESHOLD)
681 pthread_mutexattr_t mattr;
683 pthread_mutexattr_init(&mattr);
684 pthread_mutexattr_settype(&mattr, PTHREAD_MUTEX_ADAPTIVE_NP);
686 pthread_mutex_init(&g_ls_mutex, &mattr);
687 pthread_cond_init(&g_ls_cond, NULL);
689 pthread_mutexattr_destroy(&mattr);
691 sem_init(&mtsem, 0, 0);
696 sl = sort_calloc(1, sizeof(struct sort_level));
699 sl->tosort_num = nmemb;
700 sl->tosort_sz = nmemb;
702 #if defined(SORT_THREADS)
706 run_top_sort_level(sl);
710 #if defined(SORT_THREADS)
713 pthread_mutex_destroy(&g_ls_mutex);
715 nthreads = nthreads_save;
720 rxsort(struct sort_list_item **base, size_t nmemb)
723 run_sort(base, nmemb);