qsort.c

   1 /******************************************************************************/
   2 /*          pfixtools: a collection of postfix related tools                  */
   3 /*          ~~~~~~~~~                                                         */
   4 /*  ________________________________________________________________________  */
   5 /*                                                                            */
   6 /*  Redistribution and use in source and binary forms, with or without        */
   7 /*  modification, are permitted provided that the following conditions        */
   8 /*  are met:                                                                  */
   9 /*                                                                            */
  10 /*  1. Redistributions of source code must retain the above copyright         */
  11 /*     notice, this list of conditions and the following disclaimer.          */
  12 /*  2. Redistributions in binary form must reproduce the above copyright      */
  13 /*     notice, this list of conditions and the following disclaimer in the    */
  14 /*     documentation and/or other materials provided with the distribution.   */
  15 /*  3. The names of its contributors may not be used to endorse or promote    */
  16 /*     products derived from this software without specific prior written     */
  17 /*     permission.                                                            */
  18 /*                                                                            */
  19 /*  THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND   */
  20 /*  ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE     */
  21 /*  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR        */
  22 /*  PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS    */
  23 /*  BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR    */
  24 /*  CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF      */
  25 /*  SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS  */
  26 /*  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN   */
  27 /*  CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)   */
  28 /*  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF    */
  29 /*  THE POSSIBILITY OF SUCH DAMAGE.                                           */
  30 /******************************************************************************/
  31
  32 /* $Id: qsort.c,v 1.3 2003/04/11 12:31:46 mjt Exp $
  33  * Adopted from GNU glibc by Mjt.
  34  * See stdlib/qsort.c in glibc */
  35
  36 /* Copyright (C) 1991, 1992, 1996, 1997, 1999 Free Software Foundation, Inc.
  37    This file is part of the GNU C Library.
  38    Written by Douglas C. Schmidt (schmidt@ics.uci.edu).
  39
  40    The GNU C Library is free software; you can redistribute it and/or
  41    modify it under the terms of the GNU Lesser General Public
  42    License as published by the Free Software Foundation; either
  43    version 2.1 of the License, or (at your option) any later version.
  44
  45    The GNU C Library is distributed in the hope that it will be useful,
  46    but WITHOUT ANY WARRANTY; without even the implied warranty of
  47    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  48    Lesser General Public License for more details.
  49
  50    You should have received a copy of the GNU Lesser General Public
  51    License along with the GNU C Library; if not, write to the Free
  52    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  53    02111-1307 USA.  */
  54
  55 /* Usage:
  56  * first, define the following:
  57  *  QSORT_TYPE - type of array elements
  58  *  QSORT_BASE - pointer to array
  59  *  QSORT_NELT - number of elements in the array (must not be 0)
  60  *  QSORT_LT - QSORT_LT(a,b) should return true if *a < *b
  61  * and second, just #include this file into the place you want it.
  62  * Some C code will be inserted into that place, to sort array defined
  63  * by QSORT_TYPE, QSORT_BASE, QSORT_NELT and comparision routine QSORT_LT.
  64  */
  65
  66 /* Swap two items pointed to by A and B using temporary buffer t. */
  67 #define _QSORT_SWAP(a, b, t) ((void)((t = *a), (*a = *b), (*b = t)))
  68
  69 /* Discontinue quicksort algorithm when partition gets below this size.
  70    This particular magic number was chosen to work best on a Sun 4/260. */
  71 #define _QSORT_MAX_THRESH 4
  72
  73 /* Stack node declarations used to store unfulfilled partition obligations
  74  * (inlined in QSORT).
  75 typedef struct {
  76   TYPE *_lo, *_hi;
  77 } qsort_stack_node;
  78  */
  79
  80 /* The next 4 #defines implement a very fast in-line stack abstraction. */
  81 /* The stack needs log (total_elements) entries (we could even subtract
  82    log(MAX_THRESH)).  Since total_elements has type unsigned, we get as
  83    upper bound for log (total_elements):
  84    bits per byte (CHAR_BIT) * sizeof(unsigned).  */
  85 #define _QSORT_STACK_SIZE       (8 * sizeof(unsigned))
  86 #define _QSORT_PUSH(top, low, high)     \
  87         (((top->_lo = (low)), (top->_hi = (high)), ++top))
  88 #define _QSORT_POP(low, high, top)      \
  89         ((--top, (low = top->_lo), (high = top->_hi)))
  90 #define _QSORT_STACK_NOT_EMPTY  (_stack < _top)
  91
  92
  93 /* Order size using quicksort.  This implementation incorporates
  94    four optimizations discussed in Sedgewick:
  95
  96    1. Non-recursive, using an explicit stack of pointer that store the
  97       next array partition to sort.  To save time, this maximum amount
  98       of space required to store an array of SIZE_MAX is allocated on the
  99       stack.  Assuming a 32-bit (64 bit) integer for size_t, this needs
 100       only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
 101       Pretty cheap, actually.
 102
 103    2. Chose the pivot element using a median-of-three decision tree.
 104       This reduces the probability of selecting a bad pivot value and
 105       eliminates certain extraneous comparisons.
 106
 107    3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
 108       insertion sort to order the MAX_THRESH items within each partition.
 109       This is a big win, since insertion sort is faster for small, mostly
 110       sorted array segments.
 111
 112    4. The larger of the two sub-partitions is always pushed onto the
 113       stack first, with the algorithm then concentrating on the
 114       smaller partition.  This *guarantees* no more than log (total_elems)
 115       stack size is needed (actually O(1) in this case)!  */
 116
 117
 118 {
 119   QSORT_TYPE *const _base = (QSORT_BASE);
 120   const unsigned _elems = (QSORT_NELT);
 121   QSORT_TYPE _hold;
 122
 123   if (_elems > _QSORT_MAX_THRESH) {
 124     QSORT_TYPE *_lo = _base;
 125     QSORT_TYPE *_hi = _lo + _elems - 1;
 126     struct {
 127       QSORT_TYPE *_hi, *_lo;
 128     } _stack[_QSORT_STACK_SIZE], *_top = _stack + 1;
 129
 130     while (_QSORT_STACK_NOT_EMPTY) {
 131       QSORT_TYPE *_left_ptr, *_right_ptr;
 132
 133       /* Select median value from among LO, MID, and HI. Rearrange
 134          LO and HI so the three values are sorted. This lowers the
 135          probability of picking a pathological pivot value and
 136          skips a comparison for both the LEFT_PTR and RIGHT_PTR in
 137          the while loops. */
 138
 139       QSORT_TYPE *_mid = _lo + ((_hi - _lo) >> 1);
 140
 141       if (QSORT_LT (_mid, _lo))
 142         _QSORT_SWAP (_mid, _lo, _hold);
 143       if (QSORT_LT (_hi, _mid))
 144         _QSORT_SWAP (_mid, _hi, _hold);
 145       else
 146         goto _jump_over;
 147       if (QSORT_LT (_mid, _lo))
 148         _QSORT_SWAP (_mid, _lo, _hold);
 149   _jump_over:;
 150
 151       _left_ptr  = _lo + 1;
 152       _right_ptr = _hi - 1;
 153
 154       /* Here's the famous ``collapse the walls'' section of quicksort.
 155          Gotta like those tight inner loops!  They are the main reason
 156          that this algorithm runs much faster than others. */
 157       do {
 158         while (QSORT_LT (_left_ptr, _mid))
 159          ++_left_ptr;
 160
 161         while (QSORT_LT (_mid, _right_ptr))
 162           --_right_ptr;
 163
 164         if (_left_ptr < _right_ptr) {
 165           _QSORT_SWAP (_left_ptr, _right_ptr, _hold);
 166           if (_mid == _left_ptr)
 167             _mid = _right_ptr;
 168           else if (_mid == _right_ptr)
 169             _mid = _left_ptr;
 170           ++_left_ptr;
 171           --_right_ptr;
 172         }
 173         else if (_left_ptr == _right_ptr) {
 174           ++_left_ptr;
 175           --_right_ptr;
 176           break;
 177         }
 178       } while (_left_ptr <= _right_ptr);
 179
 180      /* Set up pointers for next iteration.  First determine whether
 181         left and right partitions are below the threshold size.  If so,
 182         ignore one or both.  Otherwise, push the larger partition's
 183         bounds on the stack and continue sorting the smaller one. */
 184
 185       if (_right_ptr - _lo <= _QSORT_MAX_THRESH) {
 186         if (_hi - _left_ptr <= _QSORT_MAX_THRESH)
 187           /* Ignore both small partitions. */
 188           _QSORT_POP (_lo, _hi, _top);
 189         else
 190           /* Ignore small left partition. */
 191           _lo = _left_ptr;
 192       }
 193       else if (_hi - _left_ptr <= _QSORT_MAX_THRESH)
 194         /* Ignore small right partition. */
 195         _hi = _right_ptr;
 196       else if (_right_ptr - _lo > _hi - _left_ptr) {
 197         /* Push larger left partition indices. */
 198         _QSORT_PUSH (_top, _lo, _right_ptr);
 199         _lo = _left_ptr;
 200       }
 201       else {
 202         /* Push larger right partition indices. */
 203         _QSORT_PUSH (_top, _left_ptr, _hi);
 204         _hi = _right_ptr;
 205       }
 206     }
 207   }
 208
 209   /* Once the BASE array is partially sorted by quicksort the rest
 210      is completely sorted using insertion sort, since this is efficient
 211      for partitions below MAX_THRESH size. BASE points to the
 212      beginning of the array to sort, and END_PTR points at the very
 213      last element in the array (*not* one beyond it!). */
 214
 215
 216   {
 217     QSORT_TYPE *const _end_ptr = _base + _elems - 1;
 218     QSORT_TYPE *_tmp_ptr = _base;
 219     register QSORT_TYPE *_run_ptr;
 220     QSORT_TYPE *_thresh;
 221
 222     _thresh = _base + _QSORT_MAX_THRESH;
 223     if (_thresh > _end_ptr)
 224       _thresh = _end_ptr;
 225
 226     /* Find smallest element in first threshold and place it at the
 227        array's beginning.  This is the smallest array element,
 228        and the operation speeds up insertion sort's inner loop. */
 229
 230     for (_run_ptr = _tmp_ptr + 1; _run_ptr <= _thresh; ++_run_ptr)
 231       if (QSORT_LT (_run_ptr, _tmp_ptr))
 232         _tmp_ptr = _run_ptr;
 233
 234     if (_tmp_ptr != _base)
 235       _QSORT_SWAP (_tmp_ptr, _base, _hold);
 236
 237     /* Insertion sort, running from left-hand-side
 238      * up to right-hand-side.  */
 239
 240     _run_ptr = _base + 1;
 241     while (++_run_ptr <= _end_ptr) {
 242       _tmp_ptr = _run_ptr - 1;
 243       while (QSORT_LT (_run_ptr, _tmp_ptr))
 244         --_tmp_ptr;
 245
 246       ++_tmp_ptr;
 247       if (_tmp_ptr != _run_ptr) {
 248         QSORT_TYPE *_trav = _run_ptr + 1;
 249         while (--_trav >= _run_ptr) {
 250           QSORT_TYPE *_hi, *_lo;
 251           _hold = *_trav;
 252
 253           for (_hi = _lo = _trav; --_lo >= _tmp_ptr; _hi = _lo)
 254             *_hi = *_lo;
 255           *_hi = _hold;
 256         }
 257       }
 258     }
 259   }
 260 }