ADMB Documentation  11.1.2192
 All Classes Files Functions Variables Typedefs Friends Defines
qsort.h
Go to the documentation of this file.
00001 /*
00002  * $Id: qsort.h 1750 2014-03-05 21:02:14Z johnoel $
00003  *
00004  * Modified by Derek Seiple
00005  * Copyright (c) 2010-2012 ADMB Foundation
00006  *
00007  * Adopted from GNU glibc by Mjt.
00008  * See stdlib/qsort.c in glibc
00009  */
00014 /* Copyright (C) 1991, 1992, 1996, 1997, 1999 Free Software Foundation, Inc.
00015    This file is part of the GNU C Library.
00016    Written by Douglas C. Schmidt (schmidt@ics.uci.edu).
00017 
00018    The GNU C Library is free software; you can redistribute it and/or
00019    modify it under the terms of the GNU Lesser General Public
00020    License as published by the Free Software Foundation; either
00021    version 2.1 of the License, or (at your option) any later version.
00022 
00023    The GNU C Library is distributed in the hope that it will be useful,
00024    but WITHOUT ANY WARRANTY; without even the implied warranty of
00025    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00026    Lesser General Public License for more details.
00027 
00028    You should have received a copy of the GNU Lesser General Public
00029    License along with the GNU C Library; if not, write to the Free
00030    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
00031    02111-1307 USA.  */
00032 
00033 /* in-line qsort implementation.  Differs from traditional qsort() routine
00034  * in that it is a macro, not a function, and instead of passing an address
00035  * of a comparison routine to the function, it is possible to inline
00036  * comparison routine, thus speeding up sorting a lot.
00037  *
00038  * Usage:
00039  *  #include "iqsort.h"
00040  *  #define islt(a,b) (strcmp((*a),(*b))<0)
00041  *  char *arr[];
00042  *  int n;
00043  *  QSORT(char*, arr, n, islt);
00044  *
00045  * The "prototype" and 4 arguments are:
00046  *  QSORT(TYPE,BASE,NELT,ISLT)
00047  *  1) type of each element, TYPE,
00048  *  2) address of the beginning of the array, of type TYPE*,
00049  *  3) number of elements in the array, and
00050  *  4) comparision routine.
00051  * Array pointer and number of elements are referenced only once.
00052  * This is similar to a call
00053  *  qsort(BASE,NELT,sizeof(TYPE),ISLT)
00054  * with the difference in last parameter.
00055  * Note the islt macro/routine (it receives pointers to two elements):
00056  * the only condition of interest is whenever one element is less than
00057  * another, no other conditions (greather than, equal to etc) are tested.
00058  * So, for example, to define integer sort, use:
00059  *  #define islt(a,b) ((*a)<(*b))
00060  *  QSORT(int, arr, n, islt)
00061  *
00062  * The macro could be used to implement a sorting function (see examples
00063  * below), or to implement the sorting algorithm inline.  That is, either
00064  * create a sorting function and use it whenever you want to sort something,
00065  * or use QSORT() macro directly instead a call to such routine.  Note that
00066  * the macro expands to quite some code (compiled size of int qsort on x86
00067  * is about 700..800 bytes).
00068  *
00069  * Using this macro directly it isn't possible to implement traditional
00070  * qsort() routine, because the macro assumes sizeof(element) == sizeof(TYPE),
00071  * while qsort() allows element size to be different.
00072  *
00073  * Several ready-to-use examples:
00074  *
00075  * Sorting array of integers:
00076  * void int_qsort(int *arr, unsigned n) {
00077  * #define int_lt(a,b) ((*a)<(*b))
00078  *   QSORT(int, arr, n, int_lt);
00079  * }
00080  *
00081  * Sorting array of string pointers:
00082  * void str_qsort(char *arr[], unsigned n) {
00083  * #define str_lt(a,b) (strcmp((*a),(*b)) < 0)
00084  *   QSORT(char*, arr, n, str_lt);
00085  * }
00086  *
00087  * Sorting array of structures:
00088  *
00089  * struct elt {
00090  *   int key;
00091  *   ...
00092  * };
00093  * void elt_qsort(struct elt *arr, unsigned n) {
00094  * #define elt_lt(a,b) ((a)->key < (b)->key)
00095  *  QSORT(struct elt, arr, n, elt_lt);
00096  * }
00097  *
00098  * And so on.
00099  */
00100 
00101 /* Swap two items pointed to by A and B using temporary buffer t. */
00102 #define _QSORT_SWAP(a, b, t) ((void)((t = *a), (*a = *b), (*b = t)))
00103 
00104 /* Discontinue quicksort algorithm when partition gets below this size.
00105    This particular magic number was chosen to work best on a Sun 4/260. */
00106 #define _QSORT_MAX_THRESH 4
00107 
00108 /* Stack node declarations used to store unfulfilled partition obligations
00109  * (inlined in QSORT).
00110 typedef struct {
00111   QSORT_TYPE *_lo, *_hi;
00112 } qsort_stack_node;
00113  */
00114 
00115 /* The next 4 #defines implement a very fast in-line stack abstraction. */
00116 /* The stack needs log (total_elements) entries (we could even subtract
00117    log(MAX_THRESH)).  Since total_elements has type unsigned, we get as
00118    upper bound for log (total_elements):
00119    bits per byte (CHAR_BIT) * sizeof(unsigned).  */
00120 #define _QSORT_STACK_SIZE  (8 * sizeof(unsigned))
00121 #define _QSORT_PUSH(top, low, high)  \
00122   (((top->_lo = (low)), (top->_hi = (high)), ++top))
00123 #define  _QSORT_POP(low, high, top)  \
00124   ((--top, (low = top->_lo), (high = top->_hi)))
00125 #define _QSORT_PUSH2(top, low, high)  \
00126   (((top->_lo2 = (low)), (top->_hi2 = (high)), ++top))
00127 #define  _QSORT_POP2(low, high, top)  \
00128   ((--top, (low = top->_lo2), (high = top->_hi2)))
00129 #define  _QSORT_STACK_NOT_EMPTY  (_stack < _top)
00130 
00131 /* Order size using quicksort.  This implementation incorporates
00132    four optimizations discussed in Sedgewick:
00133 
00134    1. Non-recursive, using an explicit stack of pointer that store the
00135       next array partition to sort.  To save time, this maximum amount
00136       of space required to store an array of SIZE_MAX is allocated on the
00137       stack.  Assuming a 32-bit (64 bit) integer for size_t, this needs
00138       only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
00139       Pretty cheap, actually.
00140 
00141    2. Chose the pivot element using a median-of-three decision tree.
00142       This reduces the probability of selecting a bad pivot value and
00143       eliminates certain extraneous comparisons.
00144 
00145    3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
00146       insertion sort to order the MAX_THRESH items within each partition.
00147       This is a big win, since insertion sort is faster for small, mostly
00148       sorted array segments.
00149 
00150    4. The larger of the two sub-partitions is always pushed onto the
00151       stack first, with the algorithm then concentrating on the
00152       smaller partition.  This *guarantees* no more than log (total_elems)
00153       stack size is needed (actually O(1) in this case)!  */
00154 
00155 /* The main code starts here... */
00156 #define QSORT(QSORT_TYPE,QSORT_BASE,QSORT_NELT,QSORT_LT)    \
00157 {                  \
00158   QSORT_TYPE *const _base = (QSORT_BASE);        \
00159   const unsigned _elems = (QSORT_NELT);          \
00160   QSORT_TYPE _hold;              \
00161                   \
00162   /* Don't declare two variables of type QSORT_TYPE in a single    \
00163    * statement: eg `TYPE a, b;', in case if TYPE is a pointer,    \
00164    * expands to `type* a, b;' wich isn't what we want.      \
00165    */                  \
00166                   \
00167   if (_elems > _QSORT_MAX_THRESH) {          \
00168     QSORT_TYPE *_lo = _base;            \
00169     QSORT_TYPE *_hi = _lo + _elems - 1;          \
00170     struct {                \
00171       QSORT_TYPE *_hi; QSORT_TYPE *_lo;          \
00172     } _stack[_QSORT_STACK_SIZE], *_top = _stack + 1;      \
00173                   \
00174     while (_QSORT_STACK_NOT_EMPTY) {          \
00175       QSORT_TYPE *_left_ptr; QSORT_TYPE *_right_ptr;      \
00176                   \
00177       /* Select median value from among LO, MID, and HI. Rearrange  \
00178          LO and HI so the three values are sorted. This lowers the  \
00179          probability of picking a pathological pivot value and    \
00180          skips a comparison for both the LEFT_PTR and RIGHT_PTR in  \
00181          the while loops. */            \
00182                   \
00183       QSORT_TYPE *_mid = _lo + ((_hi - _lo) >> 1);      \
00184                   \
00185       if (QSORT_LT (_mid, _lo))            \
00186         _QSORT_SWAP (_mid, _lo, _hold);          \
00187       if (QSORT_LT (_hi, _mid))  {          \
00188         _QSORT_SWAP (_mid, _hi, _hold);          \
00189         if (QSORT_LT (_mid, _lo))          \
00190           _QSORT_SWAP (_mid, _lo, _hold);        \
00191       }                 \
00192                   \
00193       _left_ptr  = _lo + 1;            \
00194       _right_ptr = _hi - 1;            \
00195                   \
00196       /* Here's the famous ``collapse the walls'' section of quicksort.  \
00197          Gotta like those tight inner loops!  They are the main reason  \
00198          that this algorithm runs much faster than others. */    \
00199       do {                \
00200         while (QSORT_LT (_left_ptr, _mid))        \
00201          ++_left_ptr;              \
00202                   \
00203         while (QSORT_LT (_mid, _right_ptr))        \
00204           --_right_ptr;              \
00205                   \
00206         if (_left_ptr < _right_ptr) {          \
00207           _QSORT_SWAP (_left_ptr, _right_ptr, _hold);      \
00208           if (_mid == _left_ptr)          \
00209             _mid = _right_ptr;            \
00210           else if (_mid == _right_ptr)          \
00211             _mid = _left_ptr;            \
00212           ++_left_ptr;              \
00213           --_right_ptr;              \
00214         }                \
00215         else if (_left_ptr == _right_ptr) {        \
00216           ++_left_ptr;              \
00217           --_right_ptr;              \
00218           break;              \
00219         }                \
00220       } while (_left_ptr <= _right_ptr);        \
00221                   \
00222      /* Set up pointers for next iteration.  First determine whether  \
00223         left and right partitions are below the threshold size.  If so,  \
00224         ignore one or both.  Otherwise, push the larger partition's  \
00225         bounds on the stack and continue sorting the smaller one. */  \
00226                   \
00227       if (_right_ptr - _lo <= _QSORT_MAX_THRESH) {      \
00228         if (_hi - _left_ptr <= _QSORT_MAX_THRESH)      \
00229           /* Ignore both small partitions. */        \
00230           _QSORT_POP (_lo, _hi, _top);          \
00231         else                \
00232           /* Ignore small left partition. */        \
00233           _lo = _left_ptr;            \
00234       }                  \
00235       else if (_hi - _left_ptr <= _QSORT_MAX_THRESH)      \
00236         /* Ignore small right partition. */        \
00237         _hi = _right_ptr;            \
00238       else if (_right_ptr - _lo > _hi - _left_ptr) {      \
00239         /* Push larger left partition indices. */      \
00240         _QSORT_PUSH (_top, _lo, _right_ptr);        \
00241         _lo = _left_ptr;            \
00242       }                  \
00243       else {                \
00244         /* Push larger right partition indices. */      \
00245         _QSORT_PUSH (_top, _left_ptr, _hi);        \
00246         _hi = _right_ptr;            \
00247       }                  \
00248     }                  \
00249   }                  \
00250                   \
00251   /* Once the BASE array is partially sorted by quicksort the rest  \
00252      is completely sorted using insertion sort, since this is efficient  \
00253      for partitions below MAX_THRESH size. BASE points to the    \
00254      beginning of the array to sort, and END_PTR points at the very  \
00255      last element in the array (*not* one beyond it!). */    \
00256                   \
00257   {                  \
00258     QSORT_TYPE *const _end_ptr = _base + _elems - 1;      \
00259     QSORT_TYPE *_tmp_ptr = _base;          \
00260     register QSORT_TYPE *_run_ptr;          \
00261     QSORT_TYPE *_thresh;            \
00262                   \
00263     _thresh = _base + _QSORT_MAX_THRESH;        \
00264     if (_thresh > _end_ptr)            \
00265       _thresh = _end_ptr;            \
00266                   \
00267     /* Find smallest element in first threshold and place it at the  \
00268        array's beginning.  This is the smallest array element,    \
00269        and the operation speeds up insertion sort's inner loop. */  \
00270                   \
00271     for (_run_ptr = _tmp_ptr + 1; _run_ptr <= _thresh; ++_run_ptr)  \
00272     {                  \
00273       if (QSORT_LT (_run_ptr, _tmp_ptr))        \
00274       {                  \
00275         _tmp_ptr = _run_ptr;            \
00276       }                  \
00277     }                  \
00278                   \
00279     if (_tmp_ptr != _base)            \
00280       _QSORT_SWAP (_tmp_ptr, _base, _hold);        \
00281                   \
00282     /* Insertion sort, running from left-hand-side      \
00283      * up to right-hand-side.  */          \
00284                   \
00285     _run_ptr = _base + 1;            \
00286     ++_run_ptr;                \
00287     while (_run_ptr <= _end_ptr) {          \
00288       _tmp_ptr = _run_ptr - 1;            \
00289       while (QSORT_LT (_run_ptr, _tmp_ptr))        \
00290         --_tmp_ptr;              \
00291                   \
00292       ++_tmp_ptr;              \
00293       if (_tmp_ptr != _run_ptr) {                                 \
00294         QSORT_TYPE *_trav = _run_ptr + 1;        \
00295         _trav--;                                                  \
00296         while ( (_trav >= _run_ptr) ) {                                  \
00297           QSORT_TYPE *_hi; QSORT_TYPE *_lo;        \
00298           _hold = *_trav;            \
00299           _hi=_lo=_trav;            \
00300           _lo--;               \
00301           while(_lo>=_tmp_ptr) {          \
00302             *_hi = *_lo;            \
00303             _hi=_lo;              \
00304             _lo--;              \
00305           }                            \
00306           *_hi = _hold;              \
00307           _trav--;                                                \
00308         }                \
00309       }                  \
00310       ++_run_ptr;              \
00311     } /*end of while*/              \
00312   }                  \
00313 }
00314 
00315 //modified by Derek Seiple
00316 #define \
00317 QSORT2(QSORT_TYPE,QSORT_TYPE2,QSORT_BASE,QSORT_BASE2,QSORT_NELT,QSORT_LT)\
00318 {                  \
00319   QSORT_TYPE *const _base = (QSORT_BASE);        \
00320   QSORT_TYPE2 *const _base2 = (QSORT_BASE2);        \
00321   const unsigned _elems = (QSORT_NELT);          \
00322   QSORT_TYPE _hold;              \
00323   QSORT_TYPE2 _hold2;              \
00324                   \
00325   /* Don't declare two variables of type QSORT_TYPE in a single    \
00326    * statement: eg `TYPE a, b;', in case if TYPE is a pointer,    \
00327    * expands to `type* a, b;' wich isn't what we want.      \
00328    */                  \
00329                   \
00330   if (_elems > _QSORT_MAX_THRESH) {          \
00331     QSORT_TYPE *_lo = _base;            \
00332     QSORT_TYPE2 *_lo2 = _base2;            \
00333     QSORT_TYPE *_hi = _lo + _elems - 1;          \
00334     QSORT_TYPE2 *_hi2 = _lo2 + _elems - 1;        \
00335     struct {                \
00336       QSORT_TYPE *_hi; QSORT_TYPE *_lo;          \
00337     } _stack[_QSORT_STACK_SIZE], *_top = _stack + 1;      \
00338     struct {                \
00339       QSORT_TYPE2 *_hi2; QSORT_TYPE2 *_lo2;        \
00340     } _stack2[_QSORT_STACK_SIZE], *_top2 = _stack2 + 1;      \
00341                   \
00342     while (_QSORT_STACK_NOT_EMPTY) {          \
00343       QSORT_TYPE *_left_ptr; QSORT_TYPE *_right_ptr;      \
00344       QSORT_TYPE2 *_left_ptr2; QSORT_TYPE2 *_right_ptr2;    \
00345                   \
00346       /* Select median value from among LO, MID, and HI. Rearrange  \
00347          LO and HI so the three values are sorted. This lowers the  \
00348          probability of picking a pathological pivot value and    \
00349          skips a comparison for both the LEFT_PTR and RIGHT_PTR in  \
00350          the while loops. */            \
00351                   \
00352       QSORT_TYPE *_mid = _lo + ((_hi - _lo) >> 1);      \
00353       QSORT_TYPE2 *_mid2 = _lo2 + ((_hi2 - _lo2) >> 1);      \
00354                   \
00355       if (QSORT_LT (_mid, _lo))            \
00356       {                  \
00357         _QSORT_SWAP (_mid, _lo, _hold);          \
00358         _QSORT_SWAP (_mid2, _lo2, _hold2);        \
00359       }                  \
00360       if (QSORT_LT (_hi, _mid))            \
00361       {                  \
00362         _QSORT_SWAP (_mid, _hi, _hold);          \
00363         _QSORT_SWAP (_mid2, _hi2, _hold2);        \
00364         if (QSORT_LT (_mid, _lo))          \
00365         {                \
00366           _QSORT_SWAP (_mid, _lo, _hold);        \
00367           _QSORT_SWAP (_mid2, _lo2, _hold2);        \
00368         }                \
00369       }                 \
00370                   \
00371       _left_ptr  = _lo + 1;            \
00372       _left_ptr2  = _lo2 + 1;            \
00373       _right_ptr = _hi - 1;            \
00374       _right_ptr2 = _hi2 - 1;            \
00375                   \
00376       /* Here's the famous ``collapse the walls'' section of quicksort.  \
00377          Gotta like those tight inner loops!  They are the main reason  \
00378          that this algorithm runs much faster than others. */    \
00379       do {                \
00380         while (QSORT_LT (_left_ptr, _mid))        \
00381         {                \
00382          ++_left_ptr;              \
00383          ++_left_ptr2;              \
00384         }                \
00385                   \
00386         while (QSORT_LT (_mid, _right_ptr))        \
00387         {                \
00388           --_right_ptr;              \
00389           --_right_ptr2;            \
00390         }                \
00391                   \
00392         if (_left_ptr < _right_ptr)          \
00393         {                \
00394           _QSORT_SWAP (_left_ptr, _right_ptr, _hold);      \
00395           _QSORT_SWAP (_left_ptr2, _right_ptr2, _hold2);    \
00396           if (_mid == _left_ptr)          \
00397           {                \
00398             _mid = _right_ptr;            \
00399             _mid2 = _right_ptr2;          \
00400           }                \
00401           else if (_mid == _right_ptr)          \
00402           {                \
00403             _mid = _left_ptr;            \
00404             _mid2 = _left_ptr2;            \
00405           }                \
00406           ++_left_ptr;              \
00407           ++_left_ptr2;              \
00408           --_right_ptr;              \
00409           --_right_ptr2;            \
00410         }                \
00411         else if (_left_ptr == _right_ptr)        \
00412         {                \
00413           ++_left_ptr;              \
00414           ++_left_ptr2;              \
00415           --_right_ptr;              \
00416           --_right_ptr2;            \
00417           break;              \
00418         }                \
00419       } while (_left_ptr <= _right_ptr);        \
00420                   \
00421      /* Set up pointers for next iteration.  First determine whether  \
00422         left and right partitions are below the threshold size.  If so,  \
00423         ignore one or both.  Otherwise, push the larger partition's  \
00424         bounds on the stack and continue sorting the smaller one. */  \
00425                   \
00426       if (_right_ptr - _lo <= _QSORT_MAX_THRESH)      \
00427       {                  \
00428         if (_hi - _left_ptr <= _QSORT_MAX_THRESH)      \
00429         {                \
00430           /* Ignore both small partitions. */        \
00431           _QSORT_POP (_lo, _hi, _top);          \
00432           _QSORT_POP2 (_lo2, _hi2, _top2);        \
00433         }                \
00434         else                \
00435         {                \
00436           /* Ignore small left partition. */        \
00437           _lo = _left_ptr;            \
00438           _lo2 = _left_ptr2;            \
00439         }                \
00440       }                  \
00441       else if (_hi - _left_ptr <= _QSORT_MAX_THRESH)      \
00442       {                  \
00443         /* Ignore small right partition. */        \
00444         _hi = _right_ptr;            \
00445         _hi2 = _right_ptr2;            \
00446       }                  \
00447       else if (_right_ptr - _lo > _hi - _left_ptr)      \
00448       {                  \
00449         /* Push larger left partition indices. */      \
00450         _QSORT_PUSH (_top, _lo, _right_ptr);        \
00451         _QSORT_PUSH2 (_top2, _lo2, _right_ptr2);      \
00452         _lo = _left_ptr;            \
00453         _lo2 = _left_ptr2;            \
00454       }                  \
00455       else                \
00456       {                  \
00457         /* Push larger right partition indices. */      \
00458         _QSORT_PUSH (_top, _left_ptr, _hi);        \
00459         _QSORT_PUSH2 (_top2, _left_ptr2, _hi2);        \
00460         _hi = _right_ptr;            \
00461         _hi2 = _right_ptr2;            \
00462       }                  \
00463     }                  \
00464   }                  \
00465                   \
00466   /* Once the BASE array is partially sorted by quicksort the rest  \
00467      is completely sorted using insertion sort, since this is efficient  \
00468      for partitions below MAX_THRESH size. BASE points to the    \
00469      beginning of the array to sort, and END_PTR points at the very  \
00470      last element in the array (*not* one beyond it!). */    \
00471                   \
00472   {                  \
00473     QSORT_TYPE *const _end_ptr = _base + _elems - 1;      \
00474     QSORT_TYPE *_tmp_ptr = _base;          \
00475     QSORT_TYPE2 *_tmp_ptr2 = _base2;          \
00476     register QSORT_TYPE *_run_ptr;          \
00477     register QSORT_TYPE2 *_run_ptr2;          \
00478     QSORT_TYPE *_thresh;            \
00479                   \
00480     _thresh = _base + _QSORT_MAX_THRESH;        \
00481     if (_thresh > _end_ptr)            \
00482     {                  \
00483       _thresh = _end_ptr;            \
00484     }                  \
00485                   \
00486     /* Find smallest element in first threshold and place it at the  \
00487        array's beginning.  This is the smallest array element,    \
00488        and the operation speeds up insertion sort's inner loop. */  \
00489                   \
00490     for (_run_ptr = _tmp_ptr + 1,_run_ptr2 = _tmp_ptr2 + 1;    \
00491          _run_ptr <= _thresh; ++_run_ptr,++_run_ptr2)      \
00492     {                  \
00493       if (QSORT_LT (_run_ptr, _tmp_ptr))        \
00494       {                  \
00495         _tmp_ptr = _run_ptr;            \
00496         _tmp_ptr2 = _run_ptr2;            \
00497       }                  \
00498     }                  \
00499                   \
00500     if (_tmp_ptr != _base)            \
00501     {                  \
00502       _QSORT_SWAP (_tmp_ptr, _base, _hold);        \
00503       _QSORT_SWAP (_tmp_ptr2, _base2, _hold2);        \
00504     }                  \
00505                   \
00506     /* Insertion sort, running from left-hand-side      \
00507      * up to right-hand-side.  */          \
00508                   \
00509     _run_ptr = _base + 1;            \
00510     _run_ptr2 = _base2 + 1;            \
00511     ++_run_ptr;                \
00512     ++_run_ptr2;              \
00513     while (_run_ptr <= _end_ptr)          \
00514     {                  \
00515       _tmp_ptr = _run_ptr - 1;            \
00516       _tmp_ptr2 = _run_ptr2 - 1;          \
00517       while (QSORT_LT (_run_ptr, _tmp_ptr))        \
00518       {                  \
00519         --_tmp_ptr;              \
00520         --_tmp_ptr2;              \
00521       }                  \
00522                   \
00523       ++_tmp_ptr;              \
00524       ++_tmp_ptr2;              \
00525       if (_tmp_ptr != _run_ptr)            \
00526       {                                         \
00527         QSORT_TYPE *_trav = _run_ptr + 1;        \
00528         QSORT_TYPE2 *_trav2 = _run_ptr2 + 1;        \
00529         _trav--;                                                  \
00530         _trav2--;                                                  \
00531         while ( (_trav >= _run_ptr) )          \
00532         {                                        \
00533           QSORT_TYPE *_hi; QSORT_TYPE *_lo;        \
00534           QSORT_TYPE2 *_hi2; QSORT_TYPE2 *_lo2;        \
00535           _hold = *_trav;            \
00536           _hold2 = *_trav2;            \
00537           _hi=_lo=_trav;            \
00538           _hi2=_lo2=_trav2;            \
00539           _lo--;               \
00540           _lo2--;               \
00541           while(_lo>=_tmp_ptr)            \
00542           {                \
00543             *_hi = *_lo;            \
00544             *_hi2 = *_lo2;            \
00545             _hi=_lo;              \
00546             _hi2=_lo2;              \
00547             _lo--;              \
00548             _lo2--;              \
00549           }                            \
00550           *_hi = _hold;              \
00551           *_hi2 = _hold2;            \
00552           _trav--;                                                \
00553           _trav2--;                                                \
00554         }                \
00555       }                  \
00556       ++_run_ptr;              \
00557       ++_run_ptr2;              \
00558     } /*end of while*/              \
00559   }                  \
00560 }