1 /*
2 * Copyright 2020 Haiku, Inc. All rights reserved.
3 * Distributed under the terms of the MIT License.
4 *
5 * Authors:
6 * Isaac Turner, turner.isaac@gmail.com
7 * Jacob Secunda, secundaja@gmail.com
8 */
9
10
11 #include <stdlib.h>
12 #include <string.h>
13
14
15 #define SORT_R_SWAP(a, b, tmp) ((tmp) = (a), (a) = (b), (b) = (tmp))
16
17
18 /* swap itemA and itemB */
19 /* itemA and itemB must not be equal! */
20 static inline void
sort_r_swap(char * __restrict itemA,char * __restrict itemB,size_t sizeOfElement)21 sort_r_swap(char* __restrict itemA, char* __restrict itemB,
22 size_t sizeOfElement)
23 {
24 char tmp;
25 char* end = itemA + sizeOfElement;
26 for (; itemA < end; itemA++, itemB++)
27 SORT_R_SWAP(* itemA, * itemB, tmp);
28 }
29
30
31 /* swap itemA and itemB if itemA > itemB */
32 /* itemA and itemB must not be equal! */
33 static inline int
sort_r_cmpswap(char * __restrict itemA,char * __restrict itemB,size_t sizeOfElement,_compare_function_qsort_r cmpFunc,void * cookie)34 sort_r_cmpswap(char* __restrict itemA, char* __restrict itemB,
35 size_t sizeOfElement, _compare_function_qsort_r cmpFunc, void* cookie)
36 {
37 if (cmpFunc(itemA, itemB, cookie) > 0) {
38 sort_r_swap(itemA, itemB, sizeOfElement);
39 return 1;
40 }
41
42 return 0;
43 }
44
45
46 /*
47 Swap consecutive blocks of bytes of size na and nb starting at memory addr
48 ptr, with the smallest swap so that the blocks are in the opposite order.
49 Blocks may be internally re-ordered e.g.
50
51 12345ab -> ab34512
52 123abc -> abc123
53 12abcde -> deabc12
54 */
55 static inline void
sort_r_swap_blocks(char * ptr,size_t numBytesA,size_t numBytesB)56 sort_r_swap_blocks(char* ptr, size_t numBytesA, size_t numBytesB)
57 {
58 if (numBytesA > 0 && numBytesB > 0) {
59 if (numBytesA > numBytesB)
60 sort_r_swap(ptr, ptr + numBytesA, numBytesB);
61 else
62 sort_r_swap(ptr, ptr + numBytesB, numBytesA);
63 }
64 }
65
66
67 /* Note: quicksort is not stable, equivalent values may be swapped */
68 static inline void
sort_r_simple(char * base,size_t numElements,size_t sizeOfElement,_compare_function_qsort_r cmpFunc,void * cookie)69 sort_r_simple(char* base, size_t numElements, size_t sizeOfElement,
70 _compare_function_qsort_r cmpFunc, void* cookie)
71 {
72 char* end = base + (numElements * sizeOfElement);
73
74 if (numElements < 10) {
75 // Insertion sort for arbitrarily small inputs
76
77 char* pivIndexA;
78 char* pivIndexB;
79 for (pivIndexA = base + sizeOfElement; pivIndexA < end;
80 pivIndexA += sizeOfElement) {
81 pivIndexB = pivIndexA;
82 while (pivIndexB > base
83 && sort_r_cmpswap(pivIndexB - sizeOfElement , pivIndexB,
84 sizeOfElement, cmpFunc, cookie)) {
85 pivIndexB -= sizeOfElement;
86 }
87 }
88 } else {
89 // Quicksort when numElements >= 10
90
91 int cmp;
92 char* nextPivCmpItem; // pl
93 char* nextPivEqualsPos; // ple
94 char* lastPivCmpItem; // pr
95 char* lastPivEqualsPos; // pre
96 char* pivot;
97 char* last = base + sizeOfElement * (numElements - 1);
98 char* tmp;
99
100 // Use median of second, middle and second-last items as pivot.
101 // First and last may have been swapped with pivot and therefore be
102 // extreme.
103 char* pivList[3];
104 pivList[0] = base + sizeOfElement;
105 pivList[1] = base + sizeOfElement * (numElements / 2);
106 pivList[2] = last - sizeOfElement;
107
108 if (cmpFunc(pivList[0], pivList[1], cookie) > 0)
109 SORT_R_SWAP(pivList[0], pivList[1], tmp);
110 if (cmpFunc(pivList[1], pivList[2], cookie) > 0) {
111 SORT_R_SWAP(pivList[1], pivList[2], tmp);
112 if (cmpFunc(pivList[0], pivList[1], cookie) > 0)
113 SORT_R_SWAP(pivList[0], pivList[1], tmp);
114 }
115
116 // Swap mid value (pivList[1]), and last element to put pivot as last
117 // element.
118 if (pivList[1] != last)
119 sort_r_swap(pivList[1], last, sizeOfElement);
120
121 // v- end (beyond the array)
122 // EEEEEELLLLLLLLuuuuuuuuGGGGGGGEEEEEEEE.
123 // ^- base ^- ple ^- pl ^- pr ^- pre ^- last (where the pivot is)
124
125 // Pivot comparison key:
126 // E = equal, L = less than, u = unknown, G = greater than, E = equal
127 pivot = last;
128 nextPivEqualsPos = nextPivCmpItem = base;
129 lastPivEqualsPos = lastPivCmpItem = last;
130
131 // Strategy:
132 // Loop into the list from the left and right at the same time to find:
133 // - an item on the left that is greater than the pivot
134 // - an item on the right that is less than the pivot
135 // Once found, they are swapped and the loop continues.
136 // Meanwhile items that are equal to the pivot are moved to the edges
137 // of the array.
138 while (nextPivCmpItem < lastPivCmpItem) {
139 // Move left hand items which are equal to the pivot to the far
140 // left. Break when we find an item that is greater than the pivot.
141 for (; nextPivCmpItem < lastPivCmpItem;
142 nextPivCmpItem += sizeOfElement) {
143 cmp = cmpFunc(nextPivCmpItem, pivot, cookie);
144 if (cmp > 0)
145 break;
146 else if (cmp == 0) {
147 if (nextPivEqualsPos < nextPivCmpItem) {
148 sort_r_swap(nextPivEqualsPos, nextPivCmpItem,
149 sizeOfElement);
150 }
151 nextPivEqualsPos += sizeOfElement;
152 }
153 }
154
155 // break if last batch of left hand items were equal to pivot
156 if (nextPivCmpItem >= lastPivCmpItem)
157 break;
158
159 // Move right hand items which are equal to the pivot to the far
160 // right. Break when we find an item that is less than the pivot.
161 for (; nextPivCmpItem < lastPivCmpItem;) {
162 lastPivCmpItem -= sizeOfElement;
163 // Move right pointer onto an unprocessed item
164 cmp = cmpFunc(lastPivCmpItem, pivot, cookie);
165 if (cmp == 0) {
166 lastPivEqualsPos -= sizeOfElement;
167 if (lastPivCmpItem < lastPivEqualsPos) {
168 sort_r_swap(lastPivCmpItem, lastPivEqualsPos,
169 sizeOfElement);
170 }
171 } else if (cmp < 0) {
172 if (nextPivCmpItem < lastPivCmpItem) {
173 sort_r_swap(nextPivCmpItem, lastPivCmpItem,
174 sizeOfElement);
175 }
176 nextPivCmpItem += sizeOfElement;
177 break;
178 }
179 }
180 }
181
182 nextPivCmpItem = lastPivCmpItem;
183 // lastPivCmpItem may have gone below nextPivCmpItem
184
185 // Now we need to go from: EEELLLGGGGEEEE
186 // to: LLLEEEEEEEGGGG
187
188 // Pivot comparison key:
189 // E = equal, L = less than, u = unknown, G = greater than, E = equal
190 sort_r_swap_blocks(base, nextPivEqualsPos - base,
191 nextPivCmpItem - nextPivEqualsPos);
192 sort_r_swap_blocks(lastPivCmpItem, lastPivEqualsPos - lastPivCmpItem,
193 end - lastPivEqualsPos);
194
195 sort_r_simple(base, (nextPivCmpItem - nextPivEqualsPos) / sizeOfElement,
196 sizeOfElement, cmpFunc, cookie);
197 sort_r_simple(end - (lastPivEqualsPos - lastPivCmpItem),
198 (lastPivEqualsPos - lastPivCmpItem) / sizeOfElement, sizeOfElement,
199 cmpFunc, cookie);
200 }
201 }
202
203
204 inline void
qsort_r(void * base,size_t numElements,size_t sizeOfElement,_compare_function_qsort_r cmpFunc,void * cookie)205 qsort_r(void* base, size_t numElements, size_t sizeOfElement,
206 _compare_function_qsort_r cmpFunc, void* cookie)
207 {
208 sort_r_simple((char*)base, numElements, sizeOfElement,
209 cmpFunc, cookie);
210 }
211