gk_mksort.h
Go to the documentation of this file.
1 
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

gtsam
Author(s):
autogenerated on Fri Nov 1 2024 03:32:38