BRL-CAD
sort.c
Go to the documentation of this file.
1 /* S O R T . C
2  * BRL-CAD
3  *
4  * Copyright (c) 2013-2014 United States Government as represented by
5  * the U.S. Army Research Laboratory.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
9  * version 2.1 as published by the Free Software Foundation.
10  *
11  * This library is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this file; see the file named COPYING for more
18  * information.
19  */
20 /* Based on OpenBSD's qsort.c rev. 251672 2013/12/17
21  * -
22  * Copyright (c) 1992, 1993
23  * The Regents of the University of California. All rights reserved.
24  *
25  * Redistribution and use in source and binary forms, with or without
26  * modification, are permitted provided that the following conditions
27  * are met:
28  * 1. Redistributions of source code must retain the above copyright
29  * notice, this list of conditions and the following disclaimer.
30  * 2. Redistributions in binary form must reproduce the above copyright
31  * notice, this list of conditions and the following disclaimer in the
32  * documentation and/or other materials provided with the distribution.
33  * 3. Neither the name of the University nor the names of its contributors
34  * may be used to endorse or promote products derived from this software
35  * without specific prior written permission.
36  *
37  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
38  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
39  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
40  * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
41  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
42  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
43  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
44  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
45  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
46  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
47  * SUCH DAMAGE.
48  */
49 
50 #include "common.h"
51 
52 #include <stdlib.h>
53 
54 #include "bu/sort.h"
55 
56 #define MIN(a, b) (a) < (b) ? a : b
57 
58 /*
59  * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
60  */
61 #define SWAPCODE(TYPE, parmi, parmj, n) \
62  { \
63  long i = (n) / sizeof (TYPE); \
64  TYPE *pi = (TYPE *) (parmi); \
65  TYPE *pj = (TYPE *) (parmj); \
66  do { \
67  TYPE t = *pi; \
68  *pi++ = *pj; \
69  *pj++ = t; \
70  } while (--i > 0); \
71  }
72 
73 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
74  es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
75 
76 
77 static void
78 swapfunc(char *a, char *b, int n, int swaptype)
79 {
80  if (swaptype <= 1)
81  SWAPCODE(long, a, b, n)
82  else
83  SWAPCODE(char, a, b, n)
84 }
85 
86 
87 #define SWAP(a, b) \
88  if (swaptype == 0) { \
89  long t = *(long *)(a); \
90  *(long *)(a) = *(long *)(b); \
91  *(long *)(b) = t; \
92  } else \
93  swapfunc(a, b, sizememb, swaptype)
94 
95 #define VECSWAP(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
96 
97 #define CMP(t, x, y) (compare((t), (x), (y)))
98 
99 
100 static char *
101 med3(char *a, char *b, char *c, int (*compare)(const void *, const void *, void *), void *thunk)
102 {
103  return CMP(a, b, thunk) < 0 ?
104  (CMP(b, c, thunk) < 0 ? b : (CMP(a, c, thunk) < 0 ? c : a))
105  :(CMP(b, c, thunk) > 0 ? b : (CMP(a, c, thunk) < 0 ? a : c));
106 }
107 
108 
109 void
110 bu_sort(void *array, size_t nummemb, size_t sizememb, int (*compare)(const void *, const void *, void *), void *context)
111 {
112  char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
113  int cmp_result;
114  int swaptype;
115  size_t d, r;
116  size_t swap_cnt;
117 
118  loop: SWAPINIT(array, sizememb);
119  swap_cnt = 0;
120  if (nummemb < 7) {
121  for (pm = (char *)array + sizememb; pm < (char *)array + nummemb * sizememb; pm += sizememb)
122  for (pl = pm;
123  pl > (char *)array && CMP(pl - sizememb, pl, context) > 0;
124  pl -= sizememb)
125  SWAP(pl, pl - sizememb);
126  return;
127  }
128  pm = (char *)array + (nummemb / 2) * sizememb;
129  if (nummemb > 7) {
130  pl = (char *)array;
131  pn = (char *)array + (nummemb - 1) * sizememb;
132  if (nummemb > 40) {
133  d = (nummemb / 8) * sizememb;
134  pl = med3(pl, pl + d, pl + 2 * d, compare, context);
135  pm = med3(pm - d, pm, pm + d, compare, context);
136  pn = med3(pn - 2 * d, pn - d, pn, compare, context);
137  }
138  pm = med3(pl, pm, pn, compare, context);
139  }
140  SWAP((char *)array, pm);
141  pa = pb = (char *)array + sizememb;
142 
143  pc = pd = (char *)array + (nummemb - 1) * sizememb;
144  for (;;) {
145  while (pb <= pc && (cmp_result = CMP(pb, array, context)) <= 0) {
146  if (cmp_result == 0) {
147  swap_cnt = 1;
148  SWAP(pa, pb);
149  pa += sizememb;
150  }
151  pb += sizememb;
152  }
153  while (pb <= pc && (cmp_result = CMP(pc, array, context)) >= 0) {
154  if (cmp_result == 0) {
155  swap_cnt = 1;
156  SWAP(pc, pd);
157  pd -= sizememb;
158  }
159  pc -= sizememb;
160  }
161  if (pb > pc)
162  break;
163  SWAP(pb, pc);
164  swap_cnt = 1;
165  pb += sizememb;
166  pc -= sizememb;
167  }
168  if (swap_cnt == 0) { /* Switch to insertion sort */
169  for (pm = (char *)array + sizememb; pm < (char *)array + nummemb * sizememb; pm += sizememb)
170  for (pl = pm;
171  pl > (char *)array && CMP(pl - sizememb, pl, context) > 0;
172  pl -= sizememb)
173  SWAP(pl, pl - sizememb);
174  return;
175  }
176 
177  pn = (char *)array + nummemb * sizememb;
178  r = MIN(pa - (char *)array, pb - pa);
179  VECSWAP((char *)array, pb - r, r);
180  r = MIN(pd - pc, (signed) (pn - pd - sizememb));
181  VECSWAP(pb, pn - r, r);
182  if ((r = pb - pa) > sizememb)
183  bu_sort(array, r / sizememb, sizememb, compare, context);
184  if ((r = pd - pc) > sizememb) {
185  /* Iterate rather than recurse to save stack space */
186  array = pn - r;
187  nummemb = r / sizememb;
188  goto loop;
189  }
190 }
#define SWAP(a, b)
Definition: sort.c:87
Header file for the BRL-CAD common definitions.
#define SWAPINIT(a, es)
Definition: sort.c:73
void bu_sort(void *array, size_t nummemb, size_t sizememb, int(*compare)(const void *, const void *, void *), void *context)
Definition: sort.c:110
#define MIN(a, b)
Definition: sort.c:56
void pd(register FILE *plotfp, double x, double y, char c)
Definition: plot3.c:127
#define SWAPCODE(TYPE, parmi, parmj, n)
Definition: sort.c:61
#define CMP(t, x, y)
Definition: sort.c:97
#define VECSWAP(a, b, n)
Definition: sort.c:95