ADMB Documentation  -a65f1c97
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
qsort.h
Go to the documentation of this file.
1 /*
2  * $Id$
3  *
4  * Modified by Derek Seiple
5  * Copyright (c) 2010-2012 ADMB Foundation
6  *
7  * Adopted from GNU glibc by Mjt.
8  * See stdlib/qsort.c in glibc
9  */
14 /* Copyright (C) 1991, 1992, 1996, 1997, 1999 Free Software Foundation, Inc.
15  This file is part of the GNU C Library.
16  Written by Douglas C. Schmidt (schmidt@ics.uci.edu).
17 
18  The GNU C Library is free software; you can redistribute it and/or
19  modify it under the terms of the GNU Lesser General Public
20  License as published by the Free Software Foundation; either
21  version 2.1 of the License, or (at your option) any later version.
22 
23  The GNU C Library is distributed in the hope that it will be useful,
24  but WITHOUT ANY WARRANTY; without even the implied warranty of
25  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
26  Lesser General Public License for more details.
27 
28  You should have received a copy of the GNU Lesser General Public
29  License along with the GNU C Library; if not, write to the Free
30  Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
31  02111-1307 USA. */
32 
33 /* in-line qsort implementation. Differs from traditional qsort() routine
34  * in that it is a macro, not a function, and instead of passing an address
35  * of a comparison routine to the function, it is possible to inline
36  * comparison routine, thus speeding up sorting a lot.
37  *
38  * Usage:
39  * #include "iqsort.h"
40  * #define islt(a,b) (strcmp((*a),(*b))<0)
41  * char *arr[];
42  * int n;
43  * QSORT(char*, arr, n, islt);
44  *
45  * The "prototype" and 4 arguments are:
46  * QSORT(TYPE,BASE,NELT,ISLT)
47  * 1) type of each element, TYPE,
48  * 2) address of the beginning of the array, of type TYPE*,
49  * 3) number of elements in the array, and
50  * 4) comparision routine.
51  * Array pointer and number of elements are referenced only once.
52  * This is similar to a call
53  * qsort(BASE,NELT,sizeof(TYPE),ISLT)
54  * with the difference in last parameter.
55  * Note the islt macro/routine (it receives pointers to two elements):
56  * the only condition of interest is whenever one element is less than
57  * another, no other conditions (greather than, equal to etc) are tested.
58  * So, for example, to define integer sort, use:
59  * #define islt(a,b) ((*a)<(*b))
60  * QSORT(int, arr, n, islt)
61  *
62  * The macro could be used to implement a sorting function (see examples
63  * below), or to implement the sorting algorithm inline. That is, either
64  * create a sorting function and use it whenever you want to sort something,
65  * or use QSORT() macro directly instead a call to such routine. Note that
66  * the macro expands to quite some code (compiled size of int qsort on x86
67  * is about 700..800 bytes).
68  *
69  * Using this macro directly it isn't possible to implement traditional
70  * qsort() routine, because the macro assumes sizeof(element) == sizeof(TYPE),
71  * while qsort() allows element size to be different.
72  *
73  * Several ready-to-use examples:
74  *
75  * Sorting array of integers:
76  * void int_qsort(int *arr, unsigned n) {
77  * #define int_lt(a,b) ((*a)<(*b))
78  * QSORT(int, arr, n, int_lt);
79  * }
80  *
81  * Sorting array of string pointers:
82  * void str_qsort(char *arr[], unsigned n) {
83  * #define str_lt(a,b) (strcmp((*a),(*b)) < 0)
84  * QSORT(char*, arr, n, str_lt);
85  * }
86  *
87  * Sorting array of structures:
88  *
89  * struct elt {
90  * int key;
91  * ...
92  * };
93  * void elt_qsort(struct elt *arr, unsigned n) {
94  * #define elt_lt(a,b) ((a)->key < (b)->key)
95  * QSORT(struct elt, arr, n, elt_lt);
96  * }
97  *
98  * And so on.
99  */
100 
101 /* Swap two items pointed to by A and B using temporary buffer t. */
102 #define _QSORT_SWAP(a, b, t) ((void)((t = *a), (*a = *b), (*b = t)))
103 
104 /* Discontinue quicksort algorithm when partition gets below this size.
105  This particular magic number was chosen to work best on a Sun 4/260. */
106 #define _QSORT_MAX_THRESH 4
107 
108 /* Stack node declarations used to store unfulfilled partition obligations
109  * (inlined in QSORT).
110 typedef struct {
111  QSORT_TYPE *_lo, *_hi;
112 } qsort_stack_node;
113  */
114 
115 /* The next 4 #defines implement a very fast in-line stack abstraction. */
116 /* The stack needs log (total_elements) entries (we could even subtract
117  log(MAX_THRESH)). Since total_elements has type unsigned, we get as
118  upper bound for log (total_elements):
119  bits per byte (CHAR_BIT) * sizeof(unsigned). */
120 #define _QSORT_STACK_SIZE (8 * sizeof(unsigned))
121 #define _QSORT_PUSH(top, low, high) \
122  (((top->_lo = (low)), (top->_hi = (high)), ++top))
123 #define _QSORT_POP(low, high, top) \
124  ((--top, (low = top->_lo), (high = top->_hi)))
125 #define _QSORT_PUSH2(top, low, high) \
126  (((top->_lo2 = (low)), (top->_hi2 = (high)), ++top))
127 #define _QSORT_POP2(low, high, top) \
128  ((--top, (low = top->_lo2), (high = top->_hi2)))
129 #define _QSORT_STACK_NOT_EMPTY (_stack < _top)
130 
131 /* Order size using quicksort. This implementation incorporates
132  four optimizations discussed in Sedgewick:
133 
134  1. Non-recursive, using an explicit stack of pointer that store the
135  next array partition to sort. To save time, this maximum amount
136  of space required to store an array of SIZE_MAX is allocated on the
137  stack. Assuming a 32-bit (64 bit) integer for size_t, this needs
138  only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
139  Pretty cheap, actually.
140 
141  2. Chose the pivot element using a median-of-three decision tree.
142  This reduces the probability of selecting a bad pivot value and
143  eliminates certain extraneous comparisons.
144 
145  3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
146  insertion sort to order the MAX_THRESH items within each partition.
147  This is a big win, since insertion sort is faster for small, mostly
148  sorted array segments.
149 
150  4. The larger of the two sub-partitions is always pushed onto the
151  stack first, with the algorithm then concentrating on the
152  smaller partition. This *guarantees* no more than log (total_elems)
153  stack size is needed (actually O(1) in this case)! */
154 
155 /* The main code starts here... */
156 #define QSORT(QSORT_TYPE,QSORT_BASE,QSORT_NELT,QSORT_LT) \
157 { \
158  QSORT_TYPE *const _base = (QSORT_BASE); \
159  const unsigned _elems = (QSORT_NELT); \
160  QSORT_TYPE _hold; \
161  \
162  /* Don't declare two variables of type QSORT_TYPE in a single \
163  * statement: eg `TYPE a, b;', in case if TYPE is a pointer, \
164  * expands to `type* a, b;' wich isn't what we want. \
165  */ \
166  \
167  if (_elems > _QSORT_MAX_THRESH) { \
168  QSORT_TYPE *_lo = _base; \
169  QSORT_TYPE *_hi = _lo + _elems - 1; \
170  struct { \
171  QSORT_TYPE *_hi; QSORT_TYPE *_lo; \
172  } _stack[_QSORT_STACK_SIZE], *_top = _stack + 1; \
173  \
174  while (_QSORT_STACK_NOT_EMPTY) { \
175  QSORT_TYPE *_left_ptr; QSORT_TYPE *_right_ptr; \
176  \
177  /* Select median value from among LO, MID, and HI. Rearrange \
178  LO and HI so the three values are sorted. This lowers the \
179  probability of picking a pathological pivot value and \
180  skips a comparison for both the LEFT_PTR and RIGHT_PTR in \
181  the while loops. */ \
182  \
183  QSORT_TYPE *_mid = _lo + ((_hi - _lo) >> 1); \
184  \
185  if (QSORT_LT (_mid, _lo)) \
186  _QSORT_SWAP (_mid, _lo, _hold); \
187  if (QSORT_LT (_hi, _mid)) { \
188  _QSORT_SWAP (_mid, _hi, _hold); \
189  if (QSORT_LT (_mid, _lo)) \
190  _QSORT_SWAP (_mid, _lo, _hold); \
191  } \
192  \
193  _left_ptr = _lo + 1; \
194  _right_ptr = _hi - 1; \
195  \
196  /* Here's the famous ``collapse the walls'' section of quicksort. \
197  Gotta like those tight inner loops! They are the main reason \
198  that this algorithm runs much faster than others. */ \
199  do { \
200  while (QSORT_LT (_left_ptr, _mid)) \
201  ++_left_ptr; \
202  \
203  while (QSORT_LT (_mid, _right_ptr)) \
204  --_right_ptr; \
205  \
206  if (_left_ptr < _right_ptr) { \
207  _QSORT_SWAP (_left_ptr, _right_ptr, _hold); \
208  if (_mid == _left_ptr) \
209  _mid = _right_ptr; \
210  else if (_mid == _right_ptr) \
211  _mid = _left_ptr; \
212  ++_left_ptr; \
213  --_right_ptr; \
214  } \
215  else if (_left_ptr == _right_ptr) { \
216  ++_left_ptr; \
217  --_right_ptr; \
218  break; \
219  } \
220  } while (_left_ptr <= _right_ptr); \
221  \
222  /* Set up pointers for next iteration. First determine whether \
223  left and right partitions are below the threshold size. If so, \
224  ignore one or both. Otherwise, push the larger partition's \
225  bounds on the stack and continue sorting the smaller one. */ \
226  \
227  if (_right_ptr - _lo <= _QSORT_MAX_THRESH) { \
228  if (_hi - _left_ptr <= _QSORT_MAX_THRESH) \
229  /* Ignore both small partitions. */ \
230  _QSORT_POP (_lo, _hi, _top); \
231  else \
232  /* Ignore small left partition. */ \
233  _lo = _left_ptr; \
234  } \
235  else if (_hi - _left_ptr <= _QSORT_MAX_THRESH) \
236  /* Ignore small right partition. */ \
237  _hi = _right_ptr; \
238  else if (_right_ptr - _lo > _hi - _left_ptr) { \
239  /* Push larger left partition indices. */ \
240  _QSORT_PUSH (_top, _lo, _right_ptr); \
241  _lo = _left_ptr; \
242  } \
243  else { \
244  /* Push larger right partition indices. */ \
245  _QSORT_PUSH (_top, _left_ptr, _hi); \
246  _hi = _right_ptr; \
247  } \
248  } \
249  } \
250  \
251  /* Once the BASE array is partially sorted by quicksort the rest \
252  is completely sorted using insertion sort, since this is efficient \
253  for partitions below MAX_THRESH size. BASE points to the \
254  beginning of the array to sort, and END_PTR points at the very \
255  last element in the array (*not* one beyond it!). */ \
256  \
257  { \
258  QSORT_TYPE *const _end_ptr = _base + _elems - 1; \
259  QSORT_TYPE *_tmp_ptr = _base; \
260  QSORT_TYPE *_run_ptr; \
261  QSORT_TYPE *_thresh; \
262  \
263  _thresh = _base + _QSORT_MAX_THRESH; \
264  if (_thresh > _end_ptr) \
265  _thresh = _end_ptr; \
266  \
267  /* Find smallest element in first threshold and place it at the \
268  array's beginning. This is the smallest array element, \
269  and the operation speeds up insertion sort's inner loop. */ \
270  \
271  for (_run_ptr = _tmp_ptr + 1; _run_ptr <= _thresh; ++_run_ptr) \
272  { \
273  if (QSORT_LT (_run_ptr, _tmp_ptr)) \
274  { \
275  _tmp_ptr = _run_ptr; \
276  } \
277  } \
278  \
279  if (_tmp_ptr != _base) \
280  _QSORT_SWAP (_tmp_ptr, _base, _hold); \
281  \
282  /* Insertion sort, running from left-hand-side \
283  * up to right-hand-side. */ \
284  \
285  _run_ptr = _base + 1; \
286  ++_run_ptr; \
287  while (_run_ptr <= _end_ptr) { \
288  _tmp_ptr = _run_ptr - 1; \
289  while (QSORT_LT (_run_ptr, _tmp_ptr)) \
290  --_tmp_ptr; \
291  \
292  ++_tmp_ptr; \
293  if (_tmp_ptr != _run_ptr) { \
294  QSORT_TYPE *_trav = _run_ptr + 1; \
295  _trav--; \
296  while ( (_trav >= _run_ptr) ) { \
297  QSORT_TYPE *_hi; QSORT_TYPE *_lo; \
298  _hold = *_trav; \
299  _hi=_lo=_trav; \
300  _lo--; \
301  while(_lo>=_tmp_ptr) { \
302  *_hi = *_lo; \
303  _hi=_lo; \
304  _lo--; \
305  } \
306  *_hi = _hold; \
307  _trav--; \
308  } \
309  } \
310  ++_run_ptr; \
311  } /*end of while*/ \
312  } \
313 }
314 
315 //modified by Derek Seiple
316 #define \
317 QSORT2(QSORT_TYPE,QSORT_TYPE2,QSORT_BASE,QSORT_BASE2,QSORT_NELT,QSORT_LT)\
318 { \
319  QSORT_TYPE *const _base = (QSORT_BASE); \
320  QSORT_TYPE2 *const _base2 = (QSORT_BASE2); \
321  const unsigned _elems = (QSORT_NELT); \
322  QSORT_TYPE _hold; \
323  QSORT_TYPE2 _hold2; \
324  \
325  /* Don't declare two variables of type QSORT_TYPE in a single \
326  * statement: eg `TYPE a, b;', in case if TYPE is a pointer, \
327  * expands to `type* a, b;' wich isn't what we want. \
328  */ \
329  \
330  if (_elems > _QSORT_MAX_THRESH) { \
331  QSORT_TYPE *_lo = _base; \
332  QSORT_TYPE2 *_lo2 = _base2; \
333  QSORT_TYPE *_hi = _lo + _elems - 1; \
334  QSORT_TYPE2 *_hi2 = _lo2 + _elems - 1; \
335  struct { \
336  QSORT_TYPE *_hi; QSORT_TYPE *_lo; \
337  } _stack[_QSORT_STACK_SIZE], *_top = _stack + 1; \
338  struct { \
339  QSORT_TYPE2 *_hi2; QSORT_TYPE2 *_lo2; \
340  } _stack2[_QSORT_STACK_SIZE], *_top2 = _stack2 + 1; \
341  \
342  while (_QSORT_STACK_NOT_EMPTY) { \
343  QSORT_TYPE *_left_ptr; QSORT_TYPE *_right_ptr; \
344  QSORT_TYPE2 *_left_ptr2; QSORT_TYPE2 *_right_ptr2; \
345  \
346  /* Select median value from among LO, MID, and HI. Rearrange \
347  LO and HI so the three values are sorted. This lowers the \
348  probability of picking a pathological pivot value and \
349  skips a comparison for both the LEFT_PTR and RIGHT_PTR in \
350  the while loops. */ \
351  \
352  QSORT_TYPE *_mid = _lo + ((_hi - _lo) >> 1); \
353  QSORT_TYPE2 *_mid2 = _lo2 + ((_hi2 - _lo2) >> 1); \
354  \
355  if (QSORT_LT (_mid, _lo)) \
356  { \
357  _QSORT_SWAP (_mid, _lo, _hold); \
358  _QSORT_SWAP (_mid2, _lo2, _hold2); \
359  } \
360  if (QSORT_LT (_hi, _mid)) \
361  { \
362  _QSORT_SWAP (_mid, _hi, _hold); \
363  _QSORT_SWAP (_mid2, _hi2, _hold2); \
364  if (QSORT_LT (_mid, _lo)) \
365  { \
366  _QSORT_SWAP (_mid, _lo, _hold); \
367  _QSORT_SWAP (_mid2, _lo2, _hold2); \
368  } \
369  } \
370  \
371  _left_ptr = _lo + 1; \
372  _left_ptr2 = _lo2 + 1; \
373  _right_ptr = _hi - 1; \
374  _right_ptr2 = _hi2 - 1; \
375  \
376  /* Here's the famous ``collapse the walls'' section of quicksort. \
377  Gotta like those tight inner loops! They are the main reason \
378  that this algorithm runs much faster than others. */ \
379  do { \
380  while (QSORT_LT (_left_ptr, _mid)) \
381  { \
382  ++_left_ptr; \
383  ++_left_ptr2; \
384  } \
385  \
386  while (QSORT_LT (_mid, _right_ptr)) \
387  { \
388  --_right_ptr; \
389  --_right_ptr2; \
390  } \
391  \
392  if (_left_ptr < _right_ptr) \
393  { \
394  _QSORT_SWAP (_left_ptr, _right_ptr, _hold); \
395  _QSORT_SWAP (_left_ptr2, _right_ptr2, _hold2); \
396  if (_mid == _left_ptr) \
397  { \
398  _mid = _right_ptr; \
399  _mid2 = _right_ptr2; \
400  } \
401  else if (_mid == _right_ptr) \
402  { \
403  _mid = _left_ptr; \
404  _mid2 = _left_ptr2; \
405  } \
406  ++_left_ptr; \
407  ++_left_ptr2; \
408  --_right_ptr; \
409  --_right_ptr2; \
410  } \
411  else if (_left_ptr == _right_ptr) \
412  { \
413  ++_left_ptr; \
414  ++_left_ptr2; \
415  --_right_ptr; \
416  --_right_ptr2; \
417  break; \
418  } \
419  } while (_left_ptr <= _right_ptr); \
420  \
421  /* Set up pointers for next iteration. First determine whether \
422  left and right partitions are below the threshold size. If so, \
423  ignore one or both. Otherwise, push the larger partition's \
424  bounds on the stack and continue sorting the smaller one. */ \
425  \
426  if (_right_ptr - _lo <= _QSORT_MAX_THRESH) \
427  { \
428  if (_hi - _left_ptr <= _QSORT_MAX_THRESH) \
429  { \
430  /* Ignore both small partitions. */ \
431  _QSORT_POP (_lo, _hi, _top); \
432  _QSORT_POP2 (_lo2, _hi2, _top2); \
433  } \
434  else \
435  { \
436  /* Ignore small left partition. */ \
437  _lo = _left_ptr; \
438  _lo2 = _left_ptr2; \
439  } \
440  } \
441  else if (_hi - _left_ptr <= _QSORT_MAX_THRESH) \
442  { \
443  /* Ignore small right partition. */ \
444  _hi = _right_ptr; \
445  _hi2 = _right_ptr2; \
446  } \
447  else if (_right_ptr - _lo > _hi - _left_ptr) \
448  { \
449  /* Push larger left partition indices. */ \
450  _QSORT_PUSH (_top, _lo, _right_ptr); \
451  _QSORT_PUSH2 (_top2, _lo2, _right_ptr2); \
452  _lo = _left_ptr; \
453  _lo2 = _left_ptr2; \
454  } \
455  else \
456  { \
457  /* Push larger right partition indices. */ \
458  _QSORT_PUSH (_top, _left_ptr, _hi); \
459  _QSORT_PUSH2 (_top2, _left_ptr2, _hi2); \
460  _hi = _right_ptr; \
461  _hi2 = _right_ptr2; \
462  } \
463  } \
464  } \
465  \
466  /* Once the BASE array is partially sorted by quicksort the rest \
467  is completely sorted using insertion sort, since this is efficient \
468  for partitions below MAX_THRESH size. BASE points to the \
469  beginning of the array to sort, and END_PTR points at the very \
470  last element in the array (*not* one beyond it!). */ \
471  \
472  { \
473  QSORT_TYPE *const _end_ptr = _base + _elems - 1; \
474  QSORT_TYPE *_tmp_ptr = _base; \
475  QSORT_TYPE2 *_tmp_ptr2 = _base2; \
476  QSORT_TYPE *_run_ptr; \
477  QSORT_TYPE2 *_run_ptr2; \
478  QSORT_TYPE *_thresh; \
479  \
480  _thresh = _base + _QSORT_MAX_THRESH; \
481  if (_thresh > _end_ptr) \
482  { \
483  _thresh = _end_ptr; \
484  } \
485  \
486  /* Find smallest element in first threshold and place it at the \
487  array's beginning. This is the smallest array element, \
488  and the operation speeds up insertion sort's inner loop. */ \
489  \
490  for (_run_ptr = _tmp_ptr + 1,_run_ptr2 = _tmp_ptr2 + 1; \
491  _run_ptr <= _thresh; ++_run_ptr,++_run_ptr2) \
492  { \
493  if (QSORT_LT (_run_ptr, _tmp_ptr)) \
494  { \
495  _tmp_ptr = _run_ptr; \
496  _tmp_ptr2 = _run_ptr2; \
497  } \
498  } \
499  \
500  if (_tmp_ptr != _base) \
501  { \
502  _QSORT_SWAP (_tmp_ptr, _base, _hold); \
503  _QSORT_SWAP (_tmp_ptr2, _base2, _hold2); \
504  } \
505  \
506  /* Insertion sort, running from left-hand-side \
507  * up to right-hand-side. */ \
508  \
509  _run_ptr = _base + 1; \
510  _run_ptr2 = _base2 + 1; \
511  ++_run_ptr; \
512  ++_run_ptr2; \
513  while (_run_ptr <= _end_ptr) \
514  { \
515  _tmp_ptr = _run_ptr - 1; \
516  _tmp_ptr2 = _run_ptr2 - 1; \
517  while (QSORT_LT (_run_ptr, _tmp_ptr)) \
518  { \
519  --_tmp_ptr; \
520  --_tmp_ptr2; \
521  } \
522  \
523  ++_tmp_ptr; \
524  ++_tmp_ptr2; \
525  if (_tmp_ptr != _run_ptr) \
526  { \
527  QSORT_TYPE *_trav = _run_ptr + 1; \
528  QSORT_TYPE2 *_trav2 = _run_ptr2 + 1; \
529  _trav--; \
530  _trav2--; \
531  while ( (_trav >= _run_ptr) ) \
532  { \
533  QSORT_TYPE *_hi; QSORT_TYPE *_lo; \
534  QSORT_TYPE2 *_hi2; QSORT_TYPE2 *_lo2; \
535  _hold = *_trav; \
536  _hold2 = *_trav2; \
537  _hi=_lo=_trav; \
538  _hi2=_lo2=_trav2; \
539  _lo--; \
540  _lo2--; \
541  while(_lo>=_tmp_ptr) \
542  { \
543  *_hi = *_lo; \
544  *_hi2 = *_lo2; \
545  _hi=_lo; \
546  _hi2=_lo2; \
547  _lo--; \
548  _lo2--; \
549  } \
550  *_hi = _hold; \
551  *_hi2 = _hold2; \
552  _trav--; \
553  _trav2--; \
554  } \
555  } \
556  ++_run_ptr; \
557  ++_run_ptr2; \
558  } /*end of while*/ \
559  } \
560 }
ADMB Generated on Wed Sep 7 2022 00:01:30 for ADMB Documentation by doxygen 1.8.5