1 /*! 2 \file gk_mksort.h 3 \brief Templates for the qsort routine 4 5 \date Started 3/28/07 6 \author George 7 \version\verbatim $Id: gk_mksort.h 10711 2011-08-31 22:23:04Z karypis $ \endverbatim 8 */ 9 10 11 #ifndef _GK_MKSORT_H_ 12 #define _GK_MKSORT_H_ 13 14 /* $Id: gk_mksort.h 10711 2011-08-31 22:23:04Z karypis $ 15 * Adopted from GNU glibc by Mjt. 16 * See stdlib/qsort.c in glibc */ 17 18 /* Copyright (C) 1991, 1992, 1996, 1997, 1999 Free Software Foundation, Inc. 19 This file is part of the GNU C Library. 20 Written by Douglas C. Schmidt (schmidt@ics.uci.edu). 21 22 The GNU C Library is free software; you can redistribute it and/or 23 modify it under the terms of the GNU Lesser General Public 24 License as published by the Free Software Foundation; either 25 version 2.1 of the License, or (at your option) any later version. 26 27 The GNU C Library is distributed in the hope that it will be useful, 28 but WITHOUT ANY WARRANTY; without even the implied warranty of 29 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 30 Lesser General Public License for more details. 31 32 You should have received a copy of the GNU Lesser General Public 33 License along with the GNU C Library; if not, write to the Free 34 Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 35 02111-1307 USA. */ 36 37 /* in-line qsort implementation. Differs from traditional qsort() routine 38 * in that it is a macro, not a function, and instead of passing an address 39 * of a comparision routine to the function, it is possible to inline 40 * comparision routine, thus speed up sorting alot. 41 * 42 * Usage: 43 * #include "iqsort.h" 44 * #define islt(a,b) (strcmp((*a),(*b))<0) 45 * char *arr[]; 46 * int n; 47 * GKQSORT(char*, arr, n, islt); 48 * 49 * The "prototype" and 4 arguments are: 50 * GKQSORT(TYPE,BASE,NELT,ISLT) 51 * 1) type of each element, TYPE, 52 * 2) address of the beginning of the array, of type TYPE*, 53 * 3) number of elements in the array, and 54 * 4) comparision routine. 55 * Array pointer and number of elements are referenced only once. 56 * This is similar to a call 57 * qsort(BASE,NELT,sizeof(TYPE),ISLT) 58 * with the difference in last parameter. 59 * Note the islt macro/routine (it receives pointers to two elements): 60 * the only condition of interest is whenever one element is less than 61 * another, no other conditions (greather than, equal to etc) are tested. 62 * So, for example, to define integer sort, use: 63 * #define islt(a,b) ((*a)<(*b)) 64 * GKQSORT(int, arr, n, islt) 65 * 66 * The macro could be used to implement a sorting function (see examples 67 * below), or to implement the sorting algorithm inline. That is, either 68 * create a sorting function and use it whenever you want to sort something, 69 * or use GKQSORT() macro directly instead a call to such routine. Note that 70 * the macro expands to quite some code (compiled size of int qsort on x86 71 * is about 700..800 bytes). 72 * 73 * Using this macro directly it isn't possible to implement traditional 74 * qsort() routine, because the macro assumes sizeof(element) == sizeof(TYPE), 75 * while qsort() allows element size to be different. 76 * 77 * Several ready-to-use examples: 78 * 79 * Sorting array of integers: 80 * void int_qsort(int *arr, unsigned n) { 81 * #define int_lt(a,b) ((*a)<(*b)) 82 * GKQSORT(int, arr, n, int_lt); 83 * } 84 * 85 * Sorting array of string pointers: 86 * void str_qsort(char *arr[], unsigned n) { 87 * #define str_lt(a,b) (strcmp((*a),(*b)) < 0) 88 * GKQSORT(char*, arr, n, str_lt); 89 * } 90 * 91 * Sorting array of structures: 92 * 93 * struct elt { 94 * int key; 95 * ... 96 * }; 97 * void elt_qsort(struct elt *arr, unsigned n) { 98 * #define elt_lt(a,b) ((a)->key < (b)->key) 99 * GKQSORT(struct elt, arr, n, elt_lt); 100 * } 101 * 102 * And so on. 103 */ 104 105 /* Swap two items pointed to by A and B using temporary buffer t. */ 106 #define _GKQSORT_SWAP(a, b, t) ((void)((t = *a), (*a = *b), (*b = t))) 107 108 /* Discontinue quicksort algorithm when partition gets below this size. 109 This particular magic number was chosen to work best on a Sun 4/260. */ 110 #define _GKQSORT_MAX_THRESH 4 111 112 /* The next 4 #defines implement a very fast in-line stack abstraction. */ 113 #define _GKQSORT_STACK_SIZE (8 * sizeof(size_t)) 114 #define _GKQSORT_PUSH(top, low, high) (((top->_lo = (low)), (top->_hi = (high)), ++top)) 115 #define _GKQSORT_POP(low, high, top) ((--top, (low = top->_lo), (high = top->_hi))) 116 #define _GKQSORT_STACK_NOT_EMPTY (_stack < _top) 117 118 119 /* The main code starts here... */ 120 #define GK_MKQSORT(GKQSORT_TYPE,GKQSORT_BASE,GKQSORT_NELT,GKQSORT_LT) \ 121 { \ 122 GKQSORT_TYPE *const _base = (GKQSORT_BASE); \ 123 const size_t _elems = (GKQSORT_NELT); \ 124 GKQSORT_TYPE _hold; \ 125 \ 126 if (_elems == 0) \ 127 return; \ 128 \ 129 /* Don't declare two variables of type GKQSORT_TYPE in a single \ 130 * statement: eg `TYPE a, b;', in case if TYPE is a pointer, \ 131 * expands to `type* a, b;' wich isn't what we want. \ 132 */ \ 133 \ 134 if (_elems > _GKQSORT_MAX_THRESH) { \ 135 GKQSORT_TYPE *_lo = _base; \ 136 GKQSORT_TYPE *_hi = _lo + _elems - 1; \ 137 struct { \ 138 GKQSORT_TYPE *_hi; GKQSORT_TYPE *_lo; \ 139 } _stack[_GKQSORT_STACK_SIZE], *_top = _stack + 1; \ 140 \ 141 while (_GKQSORT_STACK_NOT_EMPTY) { \ 142 GKQSORT_TYPE *_left_ptr; GKQSORT_TYPE *_right_ptr; \ 143 \ 144 /* Select median value from among LO, MID, and HI. Rearrange \ 145 LO and HI so the three values are sorted. This lowers the \ 146 probability of picking a pathological pivot value and \ 147 skips a comparison for both the LEFT_PTR and RIGHT_PTR in \ 148 the while loops. */ \ 149 \ 150 GKQSORT_TYPE *_mid = _lo + ((_hi - _lo) >> 1); \ 151 \ 152 if (GKQSORT_LT (_mid, _lo)) \ 153 _GKQSORT_SWAP (_mid, _lo, _hold); \ 154 if (GKQSORT_LT (_hi, _mid)) \ 155 _GKQSORT_SWAP (_mid, _hi, _hold); \ 156 else \ 157 goto _jump_over; \ 158 if (GKQSORT_LT (_mid, _lo)) \ 159 _GKQSORT_SWAP (_mid, _lo, _hold); \ 160 _jump_over:; \ 161 \ 162 _left_ptr = _lo + 1; \ 163 _right_ptr = _hi - 1; \ 164 \ 165 /* Here's the famous ``collapse the walls'' section of quicksort. \ 166 Gotta like those tight inner loops! They are the main reason \ 167 that this algorithm runs much faster than others. */ \ 168 do { \ 169 while (GKQSORT_LT (_left_ptr, _mid)) \ 170 ++_left_ptr; \ 171 \ 172 while (GKQSORT_LT (_mid, _right_ptr)) \ 173 --_right_ptr; \ 174 \ 175 if (_left_ptr < _right_ptr) { \ 176 _GKQSORT_SWAP (_left_ptr, _right_ptr, _hold); \ 177 if (_mid == _left_ptr) \ 178 _mid = _right_ptr; \ 179 else if (_mid == _right_ptr) \ 180 _mid = _left_ptr; \ 181 ++_left_ptr; \ 182 --_right_ptr; \ 183 } \ 184 else if (_left_ptr == _right_ptr) { \ 185 ++_left_ptr; \ 186 --_right_ptr; \ 187 break; \ 188 } \ 189 } while (_left_ptr <= _right_ptr); \ 190 \ 191 /* Set up pointers for next iteration. First determine whether \ 192 left and right partitions are below the threshold size. If so, \ 193 ignore one or both. Otherwise, push the larger partition's \ 194 bounds on the stack and continue sorting the smaller one. */ \ 195 \ 196 if (_right_ptr - _lo <= _GKQSORT_MAX_THRESH) { \ 197 if (_hi - _left_ptr <= _GKQSORT_MAX_THRESH) \ 198 /* Ignore both small partitions. */ \ 199 _GKQSORT_POP (_lo, _hi, _top); \ 200 else \ 201 /* Ignore small left partition. */ \ 202 _lo = _left_ptr; \ 203 } \ 204 else if (_hi - _left_ptr <= _GKQSORT_MAX_THRESH) \ 205 /* Ignore small right partition. */ \ 206 _hi = _right_ptr; \ 207 else if (_right_ptr - _lo > _hi - _left_ptr) { \ 208 /* Push larger left partition indices. */ \ 209 _GKQSORT_PUSH (_top, _lo, _right_ptr); \ 210 _lo = _left_ptr; \ 211 } \ 212 else { \ 213 /* Push larger right partition indices. */ \ 214 _GKQSORT_PUSH (_top, _left_ptr, _hi); \ 215 _hi = _right_ptr; \ 216 } \ 217 } \ 218 } \ 219 \ 220 /* Once the BASE array is partially sorted by quicksort the rest \ 221 is completely sorted using insertion sort, since this is efficient \ 222 for partitions below MAX_THRESH size. BASE points to the \ 223 beginning of the array to sort, and END_PTR points at the very \ 224 last element in the array (*not* one beyond it!). */ \ 225 \ 226 { \ 227 GKQSORT_TYPE *const _end_ptr = _base + _elems - 1; \ 228 GKQSORT_TYPE *_tmp_ptr = _base; \ 229 register GKQSORT_TYPE *_run_ptr; \ 230 GKQSORT_TYPE *_thresh; \ 231 \ 232 _thresh = _base + _GKQSORT_MAX_THRESH; \ 233 if (_thresh > _end_ptr) \ 234 _thresh = _end_ptr; \ 235 \ 236 /* Find smallest element in first threshold and place it at the \ 237 array's beginning. This is the smallest array element, \ 238 and the operation speeds up insertion sort's inner loop. */ \ 239 \ 240 for (_run_ptr = _tmp_ptr + 1; _run_ptr <= _thresh; ++_run_ptr) \ 241 if (GKQSORT_LT (_run_ptr, _tmp_ptr)) \ 242 _tmp_ptr = _run_ptr; \ 243 \ 244 if (_tmp_ptr != _base) \ 245 _GKQSORT_SWAP (_tmp_ptr, _base, _hold); \ 246 \ 247 /* Insertion sort, running from left-hand-side \ 248 * up to right-hand-side. */ \ 249 \ 250 _run_ptr = _base + 1; \ 251 while (++_run_ptr <= _end_ptr) { \ 252 _tmp_ptr = _run_ptr - 1; \ 253 while (GKQSORT_LT (_run_ptr, _tmp_ptr)) \ 254 --_tmp_ptr; \ 255 \ 256 ++_tmp_ptr; \ 257 if (_tmp_ptr != _run_ptr) { \ 258 GKQSORT_TYPE *_trav = _run_ptr + 1; \ 259 while (--_trav >= _run_ptr) { \ 260 GKQSORT_TYPE *_hi; GKQSORT_TYPE *_lo; \ 261 _hold = *_trav; \ 262 \ 263 for (_hi = _lo = _trav; --_lo >= _tmp_ptr; _hi = _lo) \ 264 *_hi = *_lo; \ 265 *_hi = _hold; \ 266 } \ 267 } \ 268 } \ 269 } \ 270 \ 271 } 272 273 #endif 274