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
|
#include <stddef.h>
#include <stdint.h>
#include "sorters.h"
static void swap(char *a, char *b, size_t width)
{
while (width--) {
char tmp = *a;
*a++ = *b;
*b++ = tmp;
}
}
static void reverse(char *base, size_t nmel, size_t width)
{
char *last = base + (nmel - 1) * width;
while (last > base) {
swap(base, last, width);
base += width;
last -= width;
}
}
/* rotates left */
static void rotate(char *base, size_t nmel, size_t width, size_t shift)
{
reverse(base, shift, width);
reverse(base + shift * width, nmel - shift, width);
reverse(base, nmel, width);
}
/* If a matching element exists, returns index of one of them.
If none exists, returns index where such an element should be inserted. */
static size_t binary_search(const char *needle, char *haystack, size_t nmel, size_t width, cmpfun cmp)
{
size_t baseidx = 0;
while (nmel) {
size_t tryidx = baseidx + nmel / 2;
char *try = haystack + tryidx * width;
int sign = cmp(try, needle);
if (!sign) return tryidx;
else if (sign < 0) {
baseidx = tryidx + 1;
nmel -= nmel / 2 + 1;
}
else {
nmel /= 2;
}
}
return baseidx;
}
static void distribute_buffer(char *base, size_t bufnmel, size_t sortnmel, size_t width, cmpfun cmp)
{
while (bufnmel) {
char *sorted = base + bufnmel * width;
size_t insertpos = binary_search(base, sorted, sortnmel, width, cmp);
while (insertpos < sortnmel && !cmp(base, sorted + insertpos * width)) {
insertpos++;
}
if (insertpos > 0) {
rotate(base, bufnmel + insertpos, width, bufnmel);
}
base += (insertpos + 1) * width;
bufnmel -= 1;
sortnmel -= insertpos;
}
}
#define MAX_SORTNET 8
static const uint8_t sortnet[][2] = {
/* 0: index = 0 */
/* 1: index = 0 */
/* 2: index = 0 */
{0,1},
/* 3: index = 1 */
{0,1}, {0,2}, {1,2},
/* 4: index = 4 */
{0,1}, {2,3}, {0,2}, {1,3}, {1,2},
/* 5: index = 9 */
{0,1}, {3,4}, {2,4}, {2,3}, {1,4}, {0,3}, {0,2}, {1,3}, {1,2},
/* 6: index = 18 */
{1,2}, {4,5}, {0,2}, {3,5}, {0,1}, {3,4}, {2,5}, {0,3}, {1,4}, {2,4},
{1,3}, {2,3},
/* 7: index = 30 */
{1,2}, {3,4}, {5,6}, {0,2}, {3,5}, {4,6}, {0,1}, {4,5}, {2,6}, {0,4},
{1,5}, {0,3}, {2,5}, {1,3}, {2,4}, {2,3},
/* 8: index = 46 */
{0,1}, {2,3}, {4,5}, {6,7}, {0,2}, {1,3}, {4,6}, {5,7}, {1,2}, {5,6},
{0,4}, {3,7}, {1,5}, {2,6}, {1,4}, {3,6}, {2,4}, {3,5}, {3,4},
/* 9: index = 65, if we used a sorting network this large */
};
static const uint8_t sortnet_index[] = { 0, 0, 0, 1, 4, 9, 18, 30, 46, 65 };
static void sorting_network(char *base, size_t nmel, size_t width, cmpfun cmp)
{
for (int i = sortnet_index[nmel]; i < sortnet_index[nmel+1]; i++) {
char *elem1 = base + sortnet[i][0] * width;
char *elem2 = base + sortnet[i][1] * width;
if (cmp(elem1, elem2) > 0) swap(elem1, elem2, width);
}
}
|
