source: vis_dev/cusp-1.1/src/util/qsort.c

Last change on this file was 12, checked in by cecile, 13 years ago

cusp added
File size: 7.6 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [qsort.c]
4
5  PackageName [util]
6
7  Synopsis    [Our own qsort routine.]
8
9  Author      []
10
11  Copyright   [Copyright (c) 1994-1996 The Regents of the Univ. of California.
12  All rights reserved.
13
14  Permission is hereby granted, without written agreement and without license
15  or royalty fees, to use, copy, modify, and distribute this software and its
16  documentation for any purpose, provided that the above copyright notice and
17  the following two paragraphs appear in all copies of this software.
18
19  IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
20  DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
21  OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
22  CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
23
24  THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
25  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
26  FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN
27  "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE
28  MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]
29
30******************************************************************************/
31
32#include "util.h"
33
34#ifndef lint
35static char rcsid[] UNUSED = "$Id: qsort.c,v 1.1.1.1 2008-11-14 20:40:10 hhkim Exp $";
36#endif
37
38#define         THRESH          4               /* threshold for insertion */
39#define         MTHRESH         6               /* threshold for median */
40
41static  int             (*qcmp)(const void *, const void *);
42                                                /* the comparison routine */
43static  int             qsz;                    /* size of each record */
44static  int             thresh;                 /* THRESHold in chars */
45static  int             mthresh;                /* MTHRESHold in chars */
46static  void            qst ARGS((char *base, char *max));
47
48/*---------------------------------------------------------------------------*/
49/* Definition of exported functions                                          */
50/*---------------------------------------------------------------------------*/
51
52#undef min
53#undef max
54/**Function********************************************************************
55
56  Synopsis           [Own version of the system qsort routine.]
57
58  Description [The THRESHold below is the insertion sort threshold, and has
59  been adjusted for records of size 48 bytes.  The MTHREShold is where we stop
60  finding a better median. First, set up some global parameters for qst to
61  share.  Then, quicksort with qst(), and then a cleanup insertion sort
62  ourselves.  Sound simple?  It's not...]
63
64  SideEffects        []
65
66  SeeAlso            [qst]
67
68******************************************************************************/
69void
70qsort(
71  void *vbase,
72  size_t n,
73  size_t size,
74  int (*compar)(const void *, const void *))
75{
76        register char c, *i, *j, *lo, *hi;
77        char *min, *max, *base;
78
79        if (n <= 1)
80                return;
81        base = (char *) vbase;
82        qsz = size;
83        qcmp = compar;
84        thresh = qsz * THRESH;
85        mthresh = qsz * MTHRESH;
86        max = base + n * qsz;
87        if (n >= THRESH) {
88                qst(base, max);
89                hi = base + thresh;
90        } else {
91                hi = max;
92        }
93        /*
94         * First put smallest element, which must be in the first THRESH, in
95         * the first position as a sentinel.  This is done just by searching
96         * the first THRESH elements (or the first n if n < THRESH), finding
97         * the min, and swapping it into the first position.
98         */
99        for (j = lo = base; (lo += qsz) < hi; )
100                if ((*qcmp)(j, lo) > 0)
101                        j = lo;
102        if (j != base) {
103                /* swap j into place */
104                for (i = base, hi = base + qsz; i < hi; ) {
105                        c = *j;
106                        *j++ = *i;
107                        *i++ = c;
108                }
109        }
110        /*
111         * With our sentinel in place, we now run the following hyper-fast
112         * insertion sort. For each remaining element, min, from [1] to [n-1],
113         * set hi to the index of the element AFTER which this one goes.
114         * Then, do the standard insertion sort shift on a character at a time
115         * basis for each element in the frob.
116         */
117        for (min = base; (hi = min += qsz) < max; ) {
118                while ((*qcmp)(hi -= qsz, min) > 0)
119                        /* void */;
120                if ((hi += qsz) != min) {
121                        for (lo = min + qsz; --lo >= min; ) {
122                                c = *lo;
123                                for (i = j = lo; (j -= qsz) >= hi; i = j)
124                                        *i = *j;
125                                *i = c;
126                        }
127                }
128        }
129}
130
131/*---------------------------------------------------------------------------*/
132/* Definition of static functions                                            */
133/*---------------------------------------------------------------------------*/
134
135/**Function********************************************************************
136
137  Synopsis           [Effectively perform qsort]
138
139  Description [First, find the median element, and put that one in the first
140  place as the discriminator.  (This "median" is just the median of the first,
141  last and middle elements).  (Using this median instead of the first element
142  is a big win).  Then, the usual partitioning/swapping, followed by moving the
143  discriminator into the right place.  Then, figure out the sizes of the two
144  partions, do the smaller one recursively and the larger one via a repeat of
145  this code.  Stopping when there are less than THRESH elements in a partition
146  and cleaning up with an insertion sort (in our caller) is a huge win.  All
147  data swaps are done in-line, which is space-losing but time-saving.  (And
148  there are only three places where this is done).]
149
150  SideEffects        []
151
152  SeeAlso            [qsort]
153
154******************************************************************************/
155static void
156qst(char *base, char *max)
157{
158        register char c, *i, *j, *jj;
159        register int ii;
160        char *mid, *tmp;
161        int lo, hi;
162
163        /*
164         * At the top here, lo is the number of characters of elements in the
165         * current partition.  (Which should be max - base).
166         * Find the median of the first, last, and middle element and make
167         * that the middle element.  Set j to largest of first and middle.
168         * If max is larger than that guy, then it's that guy, else compare
169         * max with loser of first and take larger.  Things are set up to
170         * prefer the middle, then the first in case of ties.
171         */
172        lo = max - base;                /* number of elements as chars */
173        do      {
174                mid = i = base + qsz * ((lo / qsz) >> 1);
175                if (lo >= mthresh) {
176                        j = ((*qcmp)((jj = base), i) > 0 ? jj : i);
177                        if ((*qcmp)(j, (tmp = max - qsz)) > 0) {
178                                /* switch to first loser */
179                                j = (j == jj ? i : jj);
180                                if ((*qcmp)(j, tmp) < 0)
181                                        j = tmp;
182                        }
183                        if (j != i) {
184                                ii = qsz;
185                                do      {
186                                        c = *i;
187                                        *i++ = *j;
188                                        *j++ = c;
189                                } while (--ii);
190                        }
191                }
192                /*
193                 * Semi-standard quicksort partitioning/swapping
194                 */
195                for (i = base, j = max - qsz; ; ) {
196                        while (i < mid && (*qcmp)(i, mid) <= 0)
197                                i += qsz;
198                        while (j > mid) {
199                                if ((*qcmp)(mid, j) <= 0) {
200                                        j -= qsz;
201                                        continue;
202                                }
203                                tmp = i + qsz;  /* value of i after swap */
204                                if (i == mid) {
205                                        /* j <-> mid, new mid is j */
206                                        mid = jj = j;
207                                } else {
208                                        /* i <-> j */
209                                        jj = j;
210                                        j -= qsz;
211                                }
212                                goto swap;
213                        }
214                        if (i == mid) {
215                                break;
216                        } else {
217                                /* i <-> mid, new mid is i */
218                                jj = mid;
219                                tmp = mid = i;  /* value of i after swap */
220                                j -= qsz;
221                        }
222                swap:
223                        ii = qsz;
224                        do      {
225                                c = *i;
226                                *i++ = *jj;
227                                *jj++ = c;
228                        } while (--ii);
229                        i = tmp;
230                }
231                /*
232                 * Look at sizes of the two partitions, do the smaller
233                 * one first by recursion, then do the larger one by
234                 * making sure lo is its size, base and max are update
235                 * correctly, and branching back.  But only repeat
236                 * (recursively or by branching) if the partition is
237                 * of at least size THRESH.
238                 */
239                i = (j = mid) + qsz;
240                if ((lo = j - base) <= (hi = max - i)) {
241                        if (lo >= thresh)
242                                qst(base, j);
243                        base = i;
244                        lo = hi;
245                } else {
246                        if (hi >= thresh)
247                                qst(i, max);
248                        max = j;
249                }
250        } while (lo >= thresh);
251}
Note: See TracBrowser for help on using the repository browser.