1/** @file
2  Quick Sort utility function.
3
4  This utility makes use of a comparison function to search arrays of
5  unspecified type. Where an argument declared as size_t nmemb specifies the
6  length of the array for a function, nmemb can have the value zero on a call
7  to that function; the comparison function is not called, a search finds no
8  matching element. Pointer arguments on such a call shall still have valid
9  values.
10
11  The implementation shall ensure that both arguments of the comparison
12  function are pointers to elements of the array.
13
14  The comparison function shall not alter the contents of the array. The
15  implementation may reorder elements of the array between calls to the
16  comparison function, but shall not alter the contents of any individual
17  element.
18
19  When the same objects (consisting of size bytes, irrespective of their
20  current positions in the array) are passed more than once to the comparison
21  function, the results shall be consistent with one another. That is, they
22  define a total ordering on the array.
23
24  A sequence point occurs immediately before and immediately after each call to
25  the comparison function, and also between any call to the comparison function
26  and any movement of the objects passed as arguments to that call.
27
28  Copyright (c) 2010, Intel Corporation. All rights reserved.<BR>
29 * Copyright (c) 1992, 1993
30 *  The Regents of the University of California.  All rights reserved.
31 *
32 * Redistribution and use in source and binary forms, with or without
33 * modification, are permitted provided that the following conditions
34 * are met:
35 * 1. Redistributions of source code must retain the above copyright
36 *    notice, this list of conditions and the following disclaimer.
37 * 2. Redistributions in binary form must reproduce the above copyright
38 *    notice, this list of conditions and the following disclaimer in the
39 *    documentation and/or other materials provided with the distribution.
40 * 4. Neither the name of the University nor the names of its contributors
41 *    may be used to endorse or promote products derived from this software
42 *    without specific prior written permission.
43 *
44 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
45 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
46 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
47 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
48 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
49 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
50 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
51 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
52 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
53 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
54 * SUCH DAMAGE.
55
56  ("$FreeBSD: src/lib/libc/stdlib/qsort.c,v 1.15.2.1.2.1 2009/10/25 01:10:29 kensmith Exp $");
57 */
58#include  <LibConfig.h>
59
60#include  <stdlib.h>
61
62typedef int    cmp_t(const void *, const void *);
63
64static __inline char  *med3(char *, char *, char *, cmp_t *);
65static __inline void   swapfunc(char *, char *, size_t, int);
66
67/*
68 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
69 */
70#define swapcode(TYPE, parmi, parmj, n) {     \
71  size_t i = (n) / sizeof (TYPE);       \
72  TYPE *pi = (TYPE *) (parmi);    \
73  TYPE *pj = (TYPE *) (parmj);    \
74  do {            \
75    TYPE  t = *pi;    \
76    *pi++ = *pj;        \
77    *pj++ = t;        \
78        } while (--i > 0);        \
79}
80
81#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
82  es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
83
84static __inline void
85swapfunc(char *a, char *b, size_t n, int swaptype)
86{
87  if(swaptype <= 1)
88    swapcode(long, a, b, n)
89  else
90    swapcode(char, a, b, n)
91}
92
93#define swap(a, b)          \
94  if (swaptype == 0) {        \
95    long t = *(long *)(a);      \
96    *(long *)(a) = *(long *)(b);    \
97    *(long *)(b) = t;     \
98  } else            \
99    swapfunc(a, b, es, swaptype)
100
101#define vecswap(a, b, n)  if ((n) > 0) swapfunc(a, b, n, swaptype)
102
103static __inline char *
104med3(char *a, char *b, char *c, cmp_t *cmp )
105{
106  return cmp(a, b) < 0 ?
107         (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
108              :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
109}
110
111/*  The qsort function sorts an array of nmemb objects, the initial element of
112    which is pointed to by base.  The size of each object is specified by size.
113
114    The contents of the array are sorted into ascending order according to a
115    comparison function pointed to by compar, which is called with two
116    arguments that point to the objects being compared. The function shall
117    return an integer less than, equal to, or greater than zero if the first
118    argument is considered to be respectively less than, equal to, or greater
119    than the second.
120
121    If two elements compare as equal, their order in the resulting sorted array
122    is unspecified.
123*/
124void
125qsort(void *a, size_t n, size_t es, cmp_t *cmp)
126{
127  char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
128  size_t d, r;
129  int cmp_result;
130  int swaptype, swap_cnt;
131
132loop: SWAPINIT(a, es);
133  swap_cnt = 0;
134  if (n < 7) {
135    for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
136      for (pl = pm;
137           pl > (char *)a && cmp(pl - es, pl) > 0;
138           pl -= es)
139        swap(pl, pl - es);
140    return;
141  }
142  pm = (char *)a + (n / 2) * es;
143  if (n > 7) {
144    pl = a;
145    pn = (char *)a + (n - 1) * es;
146    if (n > 40) {
147      d = (n / 8) * es;
148      pl = med3(pl, pl + d, pl + 2 * d, cmp);
149      pm = med3(pm - d, pm, pm + d, cmp);
150      pn = med3(pn - 2 * d, pn - d, pn, cmp);
151    }
152    pm = med3(pl, pm, pn, cmp);
153  }
154  swap(a, pm);
155  pa = pb = (char *)a + es;
156
157  pc = pd = (char *)a + (n - 1) * es;
158  for (;;) {
159    while (pb <= pc && (cmp_result = cmp(pb, a)) <= 0) {
160      if (cmp_result == 0) {
161        swap_cnt = 1;
162        swap(pa, pb);
163        pa += es;
164      }
165      pb += es;
166    }
167    while (pb <= pc && (cmp_result = cmp(pc, a)) >= 0) {
168      if (cmp_result == 0) {
169        swap_cnt = 1;
170        swap(pc, pd);
171        pd -= es;
172      }
173      pc -= es;
174    }
175    if (pb > pc)
176      break;
177    swap(pb, pc);
178    swap_cnt = 1;
179    pb += es;
180    pc -= es;
181  }
182  if (swap_cnt == 0) {  /* Switch to insertion sort */
183    for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
184      for (pl = pm;
185           pl > (char *)a && cmp(pl - es, pl) > 0;
186           pl -= es)
187        swap(pl, pl - es);
188    return;
189  }
190
191  pn = (char *)a + n * es;
192  r = MIN(pa - (char *)a, pb - pa);
193  vecswap(a, pb - r, r);
194  r = MIN((size_t)(pd - pc), ((size_t)(pn - pd)) - es);
195  vecswap(pb, pn - r, r);
196  if ((size_t)(r = pb - pa) > es)
197    qsort(a, r / es, es, cmp);
198  if ((size_t)(r = pd - pc) > es) {
199    /* Iterate rather than recurse to save stack space */
200    a = pn - r;
201    n = r / es;
202    goto loop;
203  }
204/*    qsort(pn - r, r / es, es, cmp);*/
205}
206