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! */
20static inline void
21sort_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! */
33static inline int
34sort_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*/
55static inline void
56sort_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 */
68static inline void
69sort_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
204inline void
205qsort_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