00001 00011 #ifndef _GK_MKSORT_H_ 00012 #define _GK_MKSORT_H_ 00013 00014 /* $Id: gk_mksort.h 10711 2011-08-31 22:23:04Z karypis $ 00015 * Adopted from GNU glibc by Mjt. 00016 * See stdlib/qsort.c in glibc */ 00017 00018 /* Copyright (C) 1991, 1992, 1996, 1997, 1999 Free Software Foundation, Inc. 00019 This file is part of the GNU C Library. 00020 Written by Douglas C. Schmidt (schmidt@ics.uci.edu). 00021 00022 The GNU C Library is free software; you can redistribute it and/or 00023 modify it under the terms of the GNU Lesser General Public 00024 License as published by the Free Software Foundation; either 00025 version 2.1 of the License, or (at your option) any later version. 00026 00027 The GNU C Library is distributed in the hope that it will be useful, 00028 but WITHOUT ANY WARRANTY; without even the implied warranty of 00029 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00030 Lesser General Public License for more details. 00031 00032 You should have received a copy of the GNU Lesser General Public 00033 License along with the GNU C Library; if not, write to the Free 00034 Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 00035 02111-1307 USA. */ 00036 00037 /* in-line qsort implementation. Differs from traditional qsort() routine 00038 * in that it is a macro, not a function, and instead of passing an address 00039 * of a comparision routine to the function, it is possible to inline 00040 * comparision routine, thus speed up sorting alot. 00041 * 00042 * Usage: 00043 * #include "iqsort.h" 00044 * #define islt(a,b) (strcmp((*a),(*b))<0) 00045 * char *arr[]; 00046 * int n; 00047 * GKQSORT(char*, arr, n, islt); 00048 * 00049 * The "prototype" and 4 arguments are: 00050 * GKQSORT(TYPE,BASE,NELT,ISLT) 00051 * 1) type of each element, TYPE, 00052 * 2) address of the beginning of the array, of type TYPE*, 00053 * 3) number of elements in the array, and 00054 * 4) comparision routine. 00055 * Array pointer and number of elements are referenced only once. 00056 * This is similar to a call 00057 * qsort(BASE,NELT,sizeof(TYPE),ISLT) 00058 * with the difference in last parameter. 00059 * Note the islt macro/routine (it receives pointers to two elements): 00060 * the only condition of interest is whenever one element is less than 00061 * another, no other conditions (greather than, equal to etc) are tested. 00062 * So, for example, to define integer sort, use: 00063 * #define islt(a,b) ((*a)<(*b)) 00064 * GKQSORT(int, arr, n, islt) 00065 * 00066 * The macro could be used to implement a sorting function (see examples 00067 * below), or to implement the sorting algorithm inline. That is, either 00068 * create a sorting function and use it whenever you want to sort something, 00069 * or use GKQSORT() macro directly instead a call to such routine. Note that 00070 * the macro expands to quite some code (compiled size of int qsort on x86 00071 * is about 700..800 bytes). 00072 * 00073 * Using this macro directly it isn't possible to implement traditional 00074 * qsort() routine, because the macro assumes sizeof(element) == sizeof(TYPE), 00075 * while qsort() allows element size to be different. 00076 * 00077 * Several ready-to-use examples: 00078 * 00079 * Sorting array of integers: 00080 * void int_qsort(int *arr, unsigned n) { 00081 * #define int_lt(a,b) ((*a)<(*b)) 00082 * GKQSORT(int, arr, n, int_lt); 00083 * } 00084 * 00085 * Sorting array of string pointers: 00086 * void str_qsort(char *arr[], unsigned n) { 00087 * #define str_lt(a,b) (strcmp((*a),(*b)) < 0) 00088 * GKQSORT(char*, arr, n, str_lt); 00089 * } 00090 * 00091 * Sorting array of structures: 00092 * 00093 * struct elt { 00094 * int key; 00095 * ... 00096 * }; 00097 * void elt_qsort(struct elt *arr, unsigned n) { 00098 * #define elt_lt(a,b) ((a)->key < (b)->key) 00099 * GKQSORT(struct elt, arr, n, elt_lt); 00100 * } 00101 * 00102 * And so on. 00103 */ 00104 00105 /* Swap two items pointed to by A and B using temporary buffer t. */ 00106 #define _GKQSORT_SWAP(a, b, t) ((void)((t = *a), (*a = *b), (*b = t))) 00107 00108 /* Discontinue quicksort algorithm when partition gets below this size. 00109 This particular magic number was chosen to work best on a Sun 4/260. */ 00110 #define _GKQSORT_MAX_THRESH 4 00111 00112 /* The next 4 #defines implement a very fast in-line stack abstraction. */ 00113 #define _GKQSORT_STACK_SIZE (8 * sizeof(size_t)) 00114 #define _GKQSORT_PUSH(top, low, high) (((top->_lo = (low)), (top->_hi = (high)), ++top)) 00115 #define _GKQSORT_POP(low, high, top) ((--top, (low = top->_lo), (high = top->_hi))) 00116 #define _GKQSORT_STACK_NOT_EMPTY (_stack < _top) 00117 00118 00119 /* The main code starts here... */ 00120 #define GK_MKQSORT(GKQSORT_TYPE,GKQSORT_BASE,GKQSORT_NELT,GKQSORT_LT) \ 00121 { \ 00122 GKQSORT_TYPE *const _base = (GKQSORT_BASE); \ 00123 const size_t _elems = (GKQSORT_NELT); \ 00124 GKQSORT_TYPE _hold; \ 00125 \ 00126 if (_elems == 0) \ 00127 return; \ 00128 \ 00129 /* Don't declare two variables of type GKQSORT_TYPE in a single \ 00130 * statement: eg `TYPE a, b;', in case if TYPE is a pointer, \ 00131 * expands to `type* a, b;' wich isn't what we want. \ 00132 */ \ 00133 \ 00134 if (_elems > _GKQSORT_MAX_THRESH) { \ 00135 GKQSORT_TYPE *_lo = _base; \ 00136 GKQSORT_TYPE *_hi = _lo + _elems - 1; \ 00137 struct { \ 00138 GKQSORT_TYPE *_hi; GKQSORT_TYPE *_lo; \ 00139 } _stack[_GKQSORT_STACK_SIZE], *_top = _stack + 1; \ 00140 \ 00141 while (_GKQSORT_STACK_NOT_EMPTY) { \ 00142 GKQSORT_TYPE *_left_ptr; GKQSORT_TYPE *_right_ptr; \ 00143 \ 00144 /* Select median value from among LO, MID, and HI. Rearrange \ 00145 LO and HI so the three values are sorted. This lowers the \ 00146 probability of picking a pathological pivot value and \ 00147 skips a comparison for both the LEFT_PTR and RIGHT_PTR in \ 00148 the while loops. */ \ 00149 \ 00150 GKQSORT_TYPE *_mid = _lo + ((_hi - _lo) >> 1); \ 00151 \ 00152 if (GKQSORT_LT (_mid, _lo)) \ 00153 _GKQSORT_SWAP (_mid, _lo, _hold); \ 00154 if (GKQSORT_LT (_hi, _mid)) \ 00155 _GKQSORT_SWAP (_mid, _hi, _hold); \ 00156 else \ 00157 goto _jump_over; \ 00158 if (GKQSORT_LT (_mid, _lo)) \ 00159 _GKQSORT_SWAP (_mid, _lo, _hold); \ 00160 _jump_over:; \ 00161 \ 00162 _left_ptr = _lo + 1; \ 00163 _right_ptr = _hi - 1; \ 00164 \ 00165 /* Here's the famous ``collapse the walls'' section of quicksort. \ 00166 Gotta like those tight inner loops! They are the main reason \ 00167 that this algorithm runs much faster than others. */ \ 00168 do { \ 00169 while (GKQSORT_LT (_left_ptr, _mid)) \ 00170 ++_left_ptr; \ 00171 \ 00172 while (GKQSORT_LT (_mid, _right_ptr)) \ 00173 --_right_ptr; \ 00174 \ 00175 if (_left_ptr < _right_ptr) { \ 00176 _GKQSORT_SWAP (_left_ptr, _right_ptr, _hold); \ 00177 if (_mid == _left_ptr) \ 00178 _mid = _right_ptr; \ 00179 else if (_mid == _right_ptr) \ 00180 _mid = _left_ptr; \ 00181 ++_left_ptr; \ 00182 --_right_ptr; \ 00183 } \ 00184 else if (_left_ptr == _right_ptr) { \ 00185 ++_left_ptr; \ 00186 --_right_ptr; \ 00187 break; \ 00188 } \ 00189 } while (_left_ptr <= _right_ptr); \ 00190 \ 00191 /* Set up pointers for next iteration. First determine whether \ 00192 left and right partitions are below the threshold size. If so, \ 00193 ignore one or both. Otherwise, push the larger partition's \ 00194 bounds on the stack and continue sorting the smaller one. */ \ 00195 \ 00196 if (_right_ptr - _lo <= _GKQSORT_MAX_THRESH) { \ 00197 if (_hi - _left_ptr <= _GKQSORT_MAX_THRESH) \ 00198 /* Ignore both small partitions. */ \ 00199 _GKQSORT_POP (_lo, _hi, _top); \ 00200 else \ 00201 /* Ignore small left partition. */ \ 00202 _lo = _left_ptr; \ 00203 } \ 00204 else if (_hi - _left_ptr <= _GKQSORT_MAX_THRESH) \ 00205 /* Ignore small right partition. */ \ 00206 _hi = _right_ptr; \ 00207 else if (_right_ptr - _lo > _hi - _left_ptr) { \ 00208 /* Push larger left partition indices. */ \ 00209 _GKQSORT_PUSH (_top, _lo, _right_ptr); \ 00210 _lo = _left_ptr; \ 00211 } \ 00212 else { \ 00213 /* Push larger right partition indices. */ \ 00214 _GKQSORT_PUSH (_top, _left_ptr, _hi); \ 00215 _hi = _right_ptr; \ 00216 } \ 00217 } \ 00218 } \ 00219 \ 00220 /* Once the BASE array is partially sorted by quicksort the rest \ 00221 is completely sorted using insertion sort, since this is efficient \ 00222 for partitions below MAX_THRESH size. BASE points to the \ 00223 beginning of the array to sort, and END_PTR points at the very \ 00224 last element in the array (*not* one beyond it!). */ \ 00225 \ 00226 { \ 00227 GKQSORT_TYPE *const _end_ptr = _base + _elems - 1; \ 00228 GKQSORT_TYPE *_tmp_ptr = _base; \ 00229 register GKQSORT_TYPE *_run_ptr; \ 00230 GKQSORT_TYPE *_thresh; \ 00231 \ 00232 _thresh = _base + _GKQSORT_MAX_THRESH; \ 00233 if (_thresh > _end_ptr) \ 00234 _thresh = _end_ptr; \ 00235 \ 00236 /* Find smallest element in first threshold and place it at the \ 00237 array's beginning. This is the smallest array element, \ 00238 and the operation speeds up insertion sort's inner loop. */ \ 00239 \ 00240 for (_run_ptr = _tmp_ptr + 1; _run_ptr <= _thresh; ++_run_ptr) \ 00241 if (GKQSORT_LT (_run_ptr, _tmp_ptr)) \ 00242 _tmp_ptr = _run_ptr; \ 00243 \ 00244 if (_tmp_ptr != _base) \ 00245 _GKQSORT_SWAP (_tmp_ptr, _base, _hold); \ 00246 \ 00247 /* Insertion sort, running from left-hand-side \ 00248 * up to right-hand-side. */ \ 00249 \ 00250 _run_ptr = _base + 1; \ 00251 while (++_run_ptr <= _end_ptr) { \ 00252 _tmp_ptr = _run_ptr - 1; \ 00253 while (GKQSORT_LT (_run_ptr, _tmp_ptr)) \ 00254 --_tmp_ptr; \ 00255 \ 00256 ++_tmp_ptr; \ 00257 if (_tmp_ptr != _run_ptr) { \ 00258 GKQSORT_TYPE *_trav = _run_ptr + 1; \ 00259 while (--_trav >= _run_ptr) { \ 00260 GKQSORT_TYPE *_hi; GKQSORT_TYPE *_lo; \ 00261 _hold = *_trav; \ 00262 \ 00263 for (_hi = _lo = _trav; --_lo >= _tmp_ptr; _hi = _lo) \ 00264 *_hi = *_lo; \ 00265 *_hi = _hold; \ 00266 } \ 00267 } \ 00268 } \ 00269 } \ 00270 \ 00271 } 00272 00273 #endif
1.5.5