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 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 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 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 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 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