1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
|
/*
* UCW Library -- Universal Simple Array Sorter
*
* (c) 2003--2008 Martin Mares <mj@ucw.cz>
*
* This software may be freely distributed and used according to the terms
* of the GNU Lesser General Public License.
*/
#pragma once
#include "contrib/macros.h"
/*
* This is not a normal header file, it's a generator of sorting
* routines. Each time you include it with parameters set in the
* corresponding preprocessor macros, it generates an array sorter
* with the parameters given.
*
* You might wonder why the heck do we implement our own array sorter
* instead of using qsort(). The primary reason is that qsort handles
* only continuous arrays, but we need to sort array-like data structures
* where the only way to access elements is by using an indexing macro.
* Besides that, we are more than 2 times faster.
*
* So much for advocacy, there are the parameters (those marked with [*]
* are mandatory):
*
* ASORT_PREFIX(x) [*] add a name prefix (used on all global names
* defined by the sorter)
* ASORT_KEY_TYPE [*] data type of a single array entry key
* ASORT_ELT(i) returns the key of i-th element; if this macro is not
* defined, the function gets a pointer to an array to be sorted
* ASORT_LT(x,y) x < y for ASORT_KEY_TYPE (default: "x<y")
* ASORT_SWAP(i,j) swap i-th and j-th element (default: assume _ELT
* is an l-value and swap just the keys)
* ASORT_THRESHOLD threshold for switching between quicksort and insertsort
* ASORT_EXTRA_ARGS extra arguments for the sort function (they are always
* visible in all the macros supplied above), starts with comma
*
* After including this file, a function ASORT_PREFIX(sort)(unsigned array_size)
* or ASORT_PREFIX(sort)(ASORT_KEY_TYPE *array, unsigned array_size) [if ASORT_ELT
* is not defined] is declared and all parameter macros are automatically
* undef'd.
*/
#ifndef ASORT_LT
#define ASORT_LT(x,y) ((x) < (y))
#endif
#ifndef ASORT_SWAP
#define ASORT_SWAP(i,j) do { ASORT_KEY_TYPE tmp = ASORT_ELT(i); ASORT_ELT(i)=ASORT_ELT(j); ASORT_ELT(j)=tmp; } while (0)
#endif
#ifndef ASORT_THRESHOLD
#define ASORT_THRESHOLD 8 /* Guesswork and experimentation */
#endif
#ifndef ASORT_EXTRA_ARGS
#define ASORT_EXTRA_ARGS
#endif
#ifndef ASORT_ELT
#define ASORT_ARRAY_ARG ASORT_KEY_TYPE *array,
#define ASORT_ELT(i) array[i]
#else
#define ASORT_ARRAY_ARG
#endif
/**
* The generated sorting function. If `ASORT_ELT` macro is not provided, the
* @ASORT_ARRAY_ARG is equal to `ASORT_KEY_TYPE *array` and is the array to be
* sorted. If the macro is provided, this parameter is omitted. In that case,
* you can sort global variables or pass your structure by @ASORT_EXTRA_ARGS.
**/
static void ASORT_PREFIX(sort)(ASORT_ARRAY_ARG unsigned array_size ASORT_EXTRA_ARGS)
{
struct stk { int l, r; } stack[8*sizeof(unsigned)];
int l, r, left, right, m;
unsigned sp = 0;
ASORT_KEY_TYPE pivot;
if (array_size <= 1)
return;
/* QuickSort with optimizations a'la Sedgewick, but stop at ASORT_THRESHOLD */
left = 0;
right = array_size - 1;
for(;;)
{
l = left;
r = right;
m = (l+r)/2;
if (ASORT_LT(ASORT_ELT(m), ASORT_ELT(l)))
ASORT_SWAP(l,m);
if (ASORT_LT(ASORT_ELT(r), ASORT_ELT(m)))
{
ASORT_SWAP(m,r);
if (ASORT_LT(ASORT_ELT(m), ASORT_ELT(l)))
ASORT_SWAP(l,m);
}
pivot = ASORT_ELT(m);
do
{
while (ASORT_LT(ASORT_ELT(l), pivot))
l++;
while (ASORT_LT(pivot, ASORT_ELT(r)))
r--;
if (l < r)
{
ASORT_SWAP(l,r);
l++;
r--;
}
else if (l == r)
{
l++;
r--;
}
}
while (l <= r);
if ((r - left) >= ASORT_THRESHOLD && (right - l) >= ASORT_THRESHOLD)
{
/* Both partitions ok => push the larger one */
if ((r - left) > (right - l))
{
stack[sp].l = left;
stack[sp].r = r;
left = l;
}
else
{
stack[sp].l = l;
stack[sp].r = right;
right = r;
}
sp++;
}
else if ((r - left) >= ASORT_THRESHOLD)
{
/* Left partition OK, right undersize */
right = r;
}
else if ((right - l) >= ASORT_THRESHOLD)
{
/* Right partition OK, left undersize */
left = l;
}
else
{
/* Both partitions undersize => pop */
if (!sp)
break;
sp--;
left = stack[sp].l;
right = stack[sp].r;
}
}
/*
* We have a partially sorted array, finish by insertsort. Inspired
* by qsort() in GNU libc.
*/
/* Find minimal element which will serve as a barrier */
r = MIN(array_size, ASORT_THRESHOLD);
m = 0;
for (l=1; l<r; l++)
if (ASORT_LT(ASORT_ELT(l),ASORT_ELT(m)))
m = l;
ASORT_SWAP(0,m);
/* Insertion sort */
for (m=1; m<(int)array_size; m++)
{
l=m;
while (ASORT_LT(ASORT_ELT(m),ASORT_ELT(l-1)))
l--;
while (l < m)
{
ASORT_SWAP(l,m);
l++;
}
}
}
#undef ASORT_PREFIX
#undef ASORT_KEY_TYPE
#undef ASORT_ELT
#undef ASORT_LT
#undef ASORT_SWAP
#undef ASORT_THRESHOLD
#undef ASORT_EXTRA_ARGS
#undef ASORT_ARRAY_ARG
|
