Mercurial > foo_out_sdl

comparison foosdk/sdk/foobar2000/SDK/foosort.cpp @ 1:20d02a178406 default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
*: check in everything else yay
author Paper <paper@tflc.us>
date Mon, 05 Jan 2026 02:15:46 -0500
parents
children
comparison
equal deleted inserted replaced
0:e9bb126753e7 1:20d02a178406
1 #include "foobar2000-sdk-pch.h"
2 #include "foosort.h"
3 #include "threadPool.h"
4 #include "genrand.h"
5
6 #define FOOSORT_PROFILING 0
7
8 namespace {
9 #if FOOSORT_PROFILING
10 typedef pfc::hires_timer foosort_timer;
11 #endif
12
13 class foosort {
14 public:
15 foosort(pfc::sort_callback & cb, abort_callback & a) : m_abort(a), p_callback(cb) {}
16
17 foosort fork() {
18 foosort ret ( * this );
19 ret.genrand = genrand_service::g_create();
20 return ret;
21 }
22
23 size_t myrand(size_t cnt) {
24 PFC_ASSERT(cnt == (uint32_t)cnt);
25 return genrand->genrand((uint32_t)cnt);
26 }
27
28 void squaresort(t_size const p_base, t_size const p_count) {
29 const t_size max = p_base + p_count;
30 for (t_size walk = p_base + 1; walk < max; ++walk) {
31 for (t_size prev = p_base; prev < walk; ++prev) {
32 p_callback.swap_check(prev, walk);
33 }
34 }
35 }
36
37
38 void _sort_2elem_helper(t_size & p_elem1, t_size & p_elem2) {
39 if (p_callback.compare(p_elem1, p_elem2) > 0) pfc::swap_t(p_elem1, p_elem2);
40 }
41
42 t_size _pivot_helper(t_size const p_base, t_size const p_count) {
43 PFC_ASSERT(p_count > 2);
44
45 //t_size val1 = p_base, val2 = p_base + (p_count / 2), val3 = p_base + (p_count - 1);
46
47 t_size val1 = myrand(p_count), val2 = myrand(p_count - 1), val3 = myrand(p_count - 2);
48 if (val2 >= val1) val2++;
49 if (val3 >= val1) val3++;
50 if (val3 >= val2) val3++;
51
52 val1 += p_base; val2 += p_base; val3 += p_base;
53
54 _sort_2elem_helper(val1, val2);
55 _sort_2elem_helper(val1, val3);
56 _sort_2elem_helper(val2, val3);
57
58 return val2;
59 }
60
61 void newsort(t_size const p_base, t_size const p_count, size_t concurrency) {
62 if (p_count <= 4) {
63 squaresort(p_base, p_count);
64 return;
65 }
66
67 this->m_abort.check();
68 #if FOOSORT_PROFILING
69 foosort_timer t;
70 if ( concurrency > 1 ) t.start();
71 #endif
72
73 t_size pivot = _pivot_helper(p_base, p_count);
74
75 {
76 const t_size target = p_base + p_count - 1;
77 if (pivot != target) {
78 p_callback.swap(pivot, target); pivot = target;
79 }
80 }
81
82
83 t_size partition = p_base;
84 {
85 bool asdf = false;
86 for (t_size walk = p_base; walk < pivot; ++walk) {
87 const int comp = p_callback.compare(walk, pivot);
88 bool trigger = false;
89 if (comp == 0) {
90 trigger = asdf;
91 asdf = !asdf;
92 } else if (comp < 0) {
93 trigger = true;
94 }
95 if (trigger) {
96 if (partition != walk) p_callback.swap(partition, walk);
97 partition++;
98 }
99 }
100 }
101 if (pivot != partition) {
102 p_callback.swap(pivot, partition); pivot = partition;
103 }
104
105 const auto base1 = p_base, count1 = pivot - p_base;
106 const auto base2 = pivot + 1, count2 = p_count - (pivot + 1 - p_base);
107
108 if (concurrency > 1) {
109
110 size_t total = count1 + count2;
111 size_t con1 = (size_t)((uint64_t)count1 * (uint64_t)concurrency / (uint64_t)total);
112 if (con1 < 1) con1 = 1;
113 if (con1 > concurrency - 1) con1 = concurrency - 1;
114 size_t con2 = concurrency - con1;
115
116 #if FOOSORT_PROFILING
117 FB2K_console_formatter() << "foosort pass: " << p_base << "+" << p_count << "(" << concurrency << ") took " << t.queryString();
118 FB2K_console_formatter() << "foosort forking: " << base1 << "+" << count1 << "(" << con1 << ") + " << base2 << "+" << count2 << "(" << con2 << ")";
119 #endif
120 pfc::counter cnt;
121 fb2k::cpuThreadPool::runMultiHelper([&] {
122 try {
123 switch (cnt++) {
124 case 0:
125 { foosort subsort = fork(); subsort.newsort(base1, count1, con1); }
126 break;
127 case 1:
128 newsort(base2, count2, con2);
129 break;
130 }
131 } catch (exception_aborted const &) {}
132 }, 2);
133 m_abort.check();
134 } else {
135 newsort(base1, count1, 1);
136 newsort(base2, count2, 1);
137 }
138 }
139 private:
140 abort_callback & m_abort;
141 pfc::sort_callback & p_callback;
142 genrand_service::ptr genrand = genrand_service::g_create();
143 };
144
145
146
147 }
148 namespace fb2k {
149 void sort(pfc::sort_callback & cb, size_t count, size_t concurrency, abort_callback & aborter) {
150 #ifdef FOOSORT_LIMIT_THREADS
151 if (concurrency > FOOSORT_LIMIT_THREADS) concurrency = FOOSORT_LIMIT_THREADS;
152 #endif
153 #if FOOSORT_PROFILING
154 foosort_timer t; t.start();
155 #endif
156 foosort theFooSort(cb, aborter);
157 theFooSort.newsort(0, count, concurrency);
158 #if FOOSORT_PROFILING
159 FB2K_console_formatter() << "foosort took: " << t.queryString();
160 #endif
161 }
162 }