1
#define NPY_NO_DEPRECATED_API NPY_API_VERSION
2

3
#include "npy_sort.h"
4
#include "npysort_common.h"
5
#include <stdlib.h>
6

7
/*
8
 *****************************************************************************
9
 **                            INTEGER SORTS                                **
10
 *****************************************************************************
11
 */
12

13

14
/**begin repeat
15
 *
16
 * #TYPE = BOOL, BYTE, UBYTE, SHORT, USHORT, INT, UINT, LONG, ULONG,
17
 *         LONGLONG, ULONGLONG#
18
 * #suff = bool, byte, ubyte, short, ushort, int, uint, long, ulong,
19
 *         longlong, ulonglong#
20
 * #type = npy_ubyte, npy_ubyte, npy_ubyte, npy_ushort, npy_ushort, npy_uint,
21
 *         npy_uint, npy_ulong, npy_ulong, npy_ulonglong, npy_ulonglong#
22
 * #sign = 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0#
23
 * #floating = 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0#
24
 */
25

26
// Reference: https://github.com/eloj/radix-sorting#-key-derivation
27
#if @sign@
28
    // Floating-point is currently disabled.
29
    // Floating-point tests succeed for double and float on macOS but not on Windows/Linux.
30
    // Basic sorting tests succeed but others relying on sort fail.
31
    // Possibly related to floating-point normalisation or multiple NaN reprs? Not sure.
32
    #if @floating@
33
        // For floats, we invert the key if the sign bit is set, else we invert the sign bit.
34
        #define KEY_OF(x) ((x) ^ (-((x) >> (sizeof(@type@) * 8 - 1)) | ((@type@)1 << (sizeof(@type@) * 8 - 1))))
35
    #else
36
        // For signed ints, we flip the sign bit so the negatives are below the positives.
37
        #define KEY_OF(x) ((x) ^ ((@type@)1 << (sizeof(@type@) * 8 - 1)))
38
    #endif
39
#else
40
    // For unsigned ints, the key is as-is
41
    #define KEY_OF(x) (x)
42
#endif
43

44
static inline npy_ubyte
45
nth_byte_@suff@(@type@ key, npy_intp l) {
46 1
    return (key >> (l << 3)) & 0xFF;
47
}
48

49
static @type@*
50 1
radixsort0_@suff@(@type@ *arr, @type@ *aux, npy_intp num)
51
{
52 1
    npy_intp cnt[sizeof(@type@)][1 << 8] = { { 0 } };
53
    npy_intp i;
54
    size_t l;
55 1
    @type@ key0 = KEY_OF(arr[0]);
56 1
    size_t ncols = 0;
57
    npy_ubyte cols[sizeof(@type@)];
58

59 1
    for (i = 0; i < num; i++) {
60 1
        @type@ k = KEY_OF(arr[i]);
61

62 1
        for (l = 0; l < sizeof(@type@); l++) {
63 1
            cnt[l][nth_byte_@suff@(k, l)]++;
64
        }
65
    }
66

67 1
    for (l = 0; l < sizeof(@type@); l++) {
68 1
	    if (cnt[l][nth_byte_@suff@(key0, l)] != num) {
69 1
	        cols[ncols++] = l;
70
        }
71
    }
72

73 1
    for (l = 0; l < ncols; l++) {
74
        npy_intp a = 0;
75 1
        for (i = 0; i < 256; i++) {
76 1
            npy_intp b = cnt[cols[l]][i];
77 1
            cnt[cols[l]][i] = a;
78 1
            a += b;
79
        }
80
    }
81

82 1
    for (l = 0; l < ncols; l++) {
83
        @type@* temp;
84 1
        for (i = 0; i < num; i++) {
85 1
            @type@ k = KEY_OF(arr[i]);
86 1
            npy_intp dst = cnt[cols[l]][nth_byte_@suff@(k, cols[l])]++;
87 1
            aux[dst] = arr[i];
88
        }
89

90 1
        temp = aux;
91 1
        aux = arr;
92 1
        arr = temp;
93
    }
94

95 1
    return arr;
96
}
97

98
NPY_NO_EXPORT int
99 1
radixsort_@suff@(void *start, npy_intp num, void *NPY_UNUSED(varr))
100
{
101
    void *sorted;
102
    @type@ *aux;
103 1
    @type@ *arr = start;
104
    @type@ k1, k2;
105 1
    npy_bool all_sorted = 1;
106

107 1
    if (num < 2) {
108
        return 0;
109
    }
110

111 1
    k1 = KEY_OF(arr[0]);
112 1
    for (npy_intp i = 1; i < num; i++) {
113 1
        k2 = KEY_OF(arr[i]);
114 1
        if (k1 > k2) {
115
            all_sorted = 0;
116
            break;
117
        }
118 1
        k1 = k2;
119
    }
120

121 1
    if (all_sorted) {
122
        return 0;
123
    }
124

125 1
    aux = malloc(num * sizeof(@type@));
126 1
    if (aux == NULL) {
127
        return -NPY_ENOMEM;
128
    }
129

130 1
    sorted = radixsort0_@suff@(start, aux, num);
131 1
    if (sorted != start) {
132 1
        memcpy(start, sorted, num * sizeof(@type@));
133
    }
134

135 1
    free(aux);
136 1
    return 0;
137
}
138

139
static npy_intp*
140 1
aradixsort0_@suff@(@type@ *arr, npy_intp *aux, npy_intp *tosort, npy_intp num)
141
{
142 1
    npy_intp cnt[sizeof(@type@)][1 << 8] = { { 0 } };
143
    npy_intp i;
144
    size_t l;
145 1
    @type@ key0 = KEY_OF(arr[0]);
146 1
    size_t ncols = 0;
147
    npy_ubyte cols[sizeof(@type@)];
148

149 1
    for (i = 0; i < num; i++) {
150 1
        @type@ k = KEY_OF(arr[i]);
151

152 1
        for (l = 0; l < sizeof(@type@); l++) {
153 1
            cnt[l][nth_byte_@suff@(k, l)]++;
154
        }
155
    }
156

157 1
    for (l = 0; l < sizeof(@type@); l++) {
158 1
        if (cnt[l][nth_byte_@suff@(key0, l)] != num) {
159 1
            cols[ncols++] = l;
160
        }
161
    }
162

163 1
    for (l = 0; l < ncols; l++) {
164
        npy_intp a = 0;
165 1
        for (i = 0; i < 256; i++) {
166 1
            npy_intp b = cnt[cols[l]][i];
167 1
            cnt[cols[l]][i] = a;
168 1
            a += b;
169
        }
170
    }
171

172 1
    for (l = 0; l < ncols; l++) {
173
        npy_intp* temp;
174 1
        for (i = 0; i < num; i++) {
175 1
            @type@ k = KEY_OF(arr[tosort[i]]);
176 1
            npy_intp dst = cnt[cols[l]][nth_byte_@suff@(k, cols[l])]++;
177 1
            aux[dst] = tosort[i];
178
        }
179

180 1
        temp = aux;
181 1
        aux = tosort;
182 1
        tosort = temp;
183
    }
184

185 1
    return tosort;
186
}
187

188
NPY_NO_EXPORT int
189 1
aradixsort_@suff@(void *start, npy_intp* tosort, npy_intp num, void *NPY_UNUSED(varr))
190
{
191
    npy_intp *sorted;
192
    npy_intp *aux;
193 1
    @type@ *arr = start;
194
    @type@ k1, k2;
195 1
    npy_bool all_sorted = 1;
196

197 1
    if (num < 2) {
198
        return 0;
199
    }
200

201 1
    k1 = KEY_OF(arr[tosort[0]]);
202 1
    for (npy_intp i = 1; i < num; i++) {
203 1
        k2 = KEY_OF(arr[tosort[i]]);
204 1
        if (k1 > k2) {
205
            all_sorted = 0;
206
            break;
207
        }
208 1
        k1 = k2;
209
    }
210

211 1
    if (all_sorted) {
212
        return 0;
213
    }
214

215 1
    aux = malloc(num * sizeof(npy_intp));
216 1
    if (aux == NULL) {
217
        return -NPY_ENOMEM;
218
    }
219

220 1
    sorted = aradixsort0_@suff@(start, aux, tosort, num);
221 1
    if (sorted != tosort) {
222 1
        memcpy(tosort, sorted, num * sizeof(npy_intp));
223
    }
224

225 1
    free(aux);
226 1
    return 0;
227
}
228

229
#undef KEY_OF
230

231
/**end repeat**/

Read our documentation on viewing source code .

Loading