ReactOS  0.4.14-dev-554-g2f8d847
qsort.c
Go to the documentation of this file.
1 /*-
2  * Copyright (c) 1992, 1993
3  * The Regents of the University of California. All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  * notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  * notice, this list of conditions and the following disclaimer in the
12  * documentation and/or other materials provided with the distribution.
13  * 4. Neither the name of the University nor the names of its contributors
14  * may be used to endorse or promote products derived from this software
15  * without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27  * SUCH DAMAGE.
28  */
29 
30 #include <stdlib.h>
31 #include <search.h>
32 
33 #define long intptr_t
34 
35 #define min(a, b) (a) < (b) ? (a) : (b)
36 
37 /*
38  * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
39  */
40 #define swapcode(TYPE, parmi, parmj, n) { \
41  long i = (n) / sizeof (TYPE); \
42  register TYPE *pi = (TYPE *) (parmi); \
43  register TYPE *pj = (TYPE *) (parmj); \
44  do { \
45  register TYPE t = *pi; \
46  *pi++ = *pj; \
47  *pj++ = t; \
48  } while (--i > 0); \
49 }
50 
51 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
52  es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
53 
54 static __inline void
55 swapfunc(char *a, char *b, intptr_t n, int swaptype)
56 {
57  if(swaptype <= 1)
58  swapcode(long, a, b, n)
59  else
60  swapcode(char, a, b, n)
61 }
62 
63 #define swap(a, b) \
64  if (swaptype == 0) { \
65  long t = *(long *)(a); \
66  *(long *)(a) = *(long *)(b); \
67  *(long *)(b) = t; \
68  } else \
69  swapfunc(a, b, es, swaptype)
70 
71 #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
72 
73 #define CMP(x, y) (cmp((x), (y)))
74 
75 static __inline char *
76 med3(char *a, char *b, char *c, int (__cdecl *cmp)(const void*, const void*))
77 {
78  return CMP(a, b) < 0 ?
79  (CMP(b, c) < 0 ? b : (CMP(a, c) < 0 ? c : a ))
80  :(CMP(b, c) > 0 ? b : (CMP(a, c) < 0 ? a : c ));
81 }
82 
83 /*
84  * qsort:
85  * First, set up some global parameters for qst to share. Then, quicksort
86  * with qst(), and then a cleanup insertion sort ourselves. Sound simple?
87  * It's not...
88  *
89  * @implemented
90  */
91 void
92 __cdecl
93 qsort(void *a, size_t n, size_t es, int (__cdecl *cmp)(const void*, const void*))
94 {
95  char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
96  int swaptype, swap_cnt;
97  intptr_t d, r;
98 
99 loop: SWAPINIT(a, es);
100  swap_cnt = 0;
101  if (n < 7) {
102  for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
103  for (pl = pm; pl > (char *)a && CMP(pl - es, pl) > 0;
104  pl -= es)
105  swap(pl, pl - es);
106  return;
107  }
108  pm = (char *)a + (n / 2) * es;
109  if (n > 7) {
110  pl = a;
111  pn = (char *)a + (n - 1) * es;
112  if (n > 40) {
113  d = (n / 8) * es;
114  pl = med3(pl, pl + d, pl + 2 * d, cmp);
115  pm = med3(pm - d, pm, pm + d, cmp);
116  pn = med3(pn - 2 * d, pn - d, pn, cmp);
117  }
118  pm = med3(pl, pm, pn, cmp);
119  }
120  swap(a, pm);
121  pa = pb = (char *)a + es;
122 
123  pc = pd = (char *)a + (n - 1) * es;
124  for (;;) {
125  while (pb <= pc && (r = CMP(pb, a)) <= 0) {
126  if (r == 0) {
127  swap_cnt = 1;
128  swap(pa, pb);
129  pa += es;
130  }
131  pb += es;
132  }
133  while (pb <= pc && (r = CMP(pc, a)) >= 0) {
134  if (r == 0) {
135  swap_cnt = 1;
136  swap(pc, pd);
137  pd -= es;
138  }
139  pc -= es;
140  }
141  if (pb > pc)
142  break;
143  swap(pb, pc);
144  swap_cnt = 1;
145  pb += es;
146  pc -= es;
147  }
148  if (swap_cnt == 0) { /* Switch to insertion sort */
149  for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
150  for (pl = pm; pl > (char *)a && CMP(pl - es, pl) > 0;
151  pl -= es)
152  swap(pl, pl - es);
153  return;
154  }
155 
156  pn = (char *)a + n * es;
157  r = min(pa - (char *)a, pb - pa);
158  vecswap(a, pb - r, r);
159  r = min(pd - pc, pn - pd - es);
160  vecswap(pb, pn - r, r);
161  if ((r = pb - pa) > es)
162  qsort(a, r / es, es, cmp);
163  if ((r = pd - pc) > es) {
164  /* Iterate rather than recurse to save stack space */
165  a = pn - r;
166  n = r / es;
167  goto loop;
168  }
169 }
#define swap(a, b)
Definition: qsort.c:63
#define __cdecl
Definition: accygwin.h:79
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
static LPMONITOREX pm
Definition: localmon.c:45
static __inline void swapfunc(char *a, char *b, intptr_t n, int swaptype)
Definition: qsort.c:55
GLdouble n
Definition: glext.h:7729
#define cmp(status, error)
Definition: error.c:114
#define SWAPINIT(a, es)
Definition: qsort.c:51
#define a
Definition: ke_i.h:78
#define b
Definition: ke_i.h:79
static int ** pa
Definition: server.c:126
static int pints_t pn[]
Definition: server.c:129
#define swapcode(TYPE, parmi, parmj, n)
Definition: qsort.c:40
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
#define CMP(x, y)
Definition: qsort.c:73
#define d
Definition: ke_i.h:81
int intptr_t
Definition: crtdefs.h:283
static __inline char * med3(char *a, char *b, char *c, int(__cdecl *cmp)(const void *, const void *))
Definition: qsort.c:76
const GLubyte * c
Definition: glext.h:8905
void __cdecl qsort(void *a, size_t n, size_t es, int(__cdecl *cmp)(const void *, const void *))
Definition: qsort.c:93
#define vecswap(a, b, n)
Definition: qsort.c:71
#define c
Definition: ke_i.h:80
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
#define es
Definition: i386-dis.c:431
#define min(a, b)
Definition: qsort.c:35