summaryrefslogtreecommitdiff
path: root/numpy
diff options
context:
space:
mode:
Diffstat (limited to 'numpy')
-rw-r--r--numpy/core/setup.py2
-rw-r--r--numpy/core/src/common/numpy_tag.h34
-rw-r--r--numpy/core/src/npysort/npysort_common.h4
-rw-r--r--numpy/core/src/npysort/timsort.cpp (renamed from numpy/core/src/npysort/timsort.c.src)1558
4 files changed, 1027 insertions, 571 deletions
diff --git a/numpy/core/setup.py b/numpy/core/setup.py
index 22cac1e9a..1cbb46c08 100644
--- a/numpy/core/setup.py
+++ b/numpy/core/setup.py
@@ -948,7 +948,7 @@ def configuration(parent_package='',top_path=None):
join('src', 'common', 'npy_sort.h.src'),
join('src', 'npysort', 'quicksort.c.src'),
join('src', 'npysort', 'mergesort.c.src'),
- join('src', 'npysort', 'timsort.c.src'),
+ join('src', 'npysort', 'timsort.cpp'),
join('src', 'npysort', 'heapsort.c.src'),
join('src', 'npysort', 'radixsort.cpp'),
join('src', 'common', 'npy_partition.h.src'),
diff --git a/numpy/core/src/common/numpy_tag.h b/numpy/core/src/common/numpy_tag.h
index 60e9b02cd..ee0c36cac 100644
--- a/numpy/core/src/common/numpy_tag.h
+++ b/numpy/core/src/common/numpy_tag.h
@@ -220,6 +220,40 @@ struct timedelta_tag : date_tag {
}
};
+struct string_tag {
+ using type = npy_char;
+ static constexpr NPY_TYPES type_value = NPY_STRING;
+ static int less(type const* a, type const* b, size_t len) {
+ return STRING_LT(a, b, len);
+ }
+ static int less_equal(type const* a, type const* b, size_t len) {
+ return !less(b, a, len);
+ }
+ static void swap(type* a, type* b, size_t len) {
+ STRING_SWAP(a, b, len);
+ }
+ static void copy(type * a, type const* b, size_t len) {
+ STRING_COPY(a, b, len);
+ }
+};
+
+struct unicode_tag {
+ using type = npy_ucs4;
+ static constexpr NPY_TYPES type_value = NPY_UNICODE;
+ static int less(type const* a, type const* b, size_t len) {
+ return UNICODE_LT(a, b, len);
+ }
+ static int less_equal(type const* a, type const* b, size_t len) {
+ return !less(b, a, len);
+ }
+ static void swap(type* a, type* b, size_t len) {
+ UNICODE_SWAP(a, b, len);
+ }
+ static void copy(type * a, type const* b, size_t len) {
+ UNICODE_COPY(a, b, len);
+ }
+};
+
} // namespace npy
#endif
diff --git a/numpy/core/src/npysort/npysort_common.h b/numpy/core/src/npysort/npysort_common.h
index a537fcd08..ab9f456b6 100644
--- a/numpy/core/src/npysort/npysort_common.h
+++ b/numpy/core/src/npysort/npysort_common.h
@@ -259,7 +259,7 @@ CLONGDOUBLE_LT(npy_clongdouble a, npy_clongdouble b)
NPY_INLINE static void
-STRING_COPY(char *s1, char *s2, size_t len)
+STRING_COPY(char *s1, char const*s2, size_t len)
{
memcpy(s1, s2, len);
}
@@ -295,7 +295,7 @@ STRING_LT(const char *s1, const char *s2, size_t len)
NPY_INLINE static void
-UNICODE_COPY(npy_ucs4 *s1, npy_ucs4 *s2, size_t len)
+UNICODE_COPY(npy_ucs4 *s1, npy_ucs4 const *s2, size_t len)
{
while(len--) {
*s1++ = *s2++;
diff --git a/numpy/core/src/npysort/timsort.c.src b/numpy/core/src/npysort/timsort.cpp
index 5298f5a1d..8bcd90061 100644
--- a/numpy/core/src/npysort/timsort.c.src
+++ b/numpy/core/src/npysort/timsort.cpp
@@ -26,7 +26,6 @@
* The heap sort is included for completeness.
*/
-
/* For details of Timsort, refer to
* https://github.com/python/cpython/blob/3.7/Objects/listsort.txt
*/
@@ -35,14 +34,16 @@
#include "npy_sort.h"
#include "npysort_common.h"
-#include <stdlib.h>
+#include "numpy_tag.h"
+
+#include <cstdlib>
+#include <utility>
/* enough for 32 * 1.618 ** 128 elements */
#define TIMSORT_STACK_SIZE 128
-
-
-static npy_intp compute_min_run(npy_intp num)
+static npy_intp
+compute_min_run(npy_intp num)
{
npy_intp r = 0;
@@ -59,14 +60,12 @@ typedef struct {
npy_intp l; /* length */
} run;
-
/* buffer for argsort. Declared here to avoid multiple declarations. */
typedef struct {
npy_intp *pw;
npy_intp size;
} buffer_intp;
-
/* buffer method */
static NPY_INLINE int
resize_buffer_intp(buffer_intp *buffer, npy_intp new_size)
@@ -76,16 +75,19 @@ resize_buffer_intp(buffer_intp *buffer, npy_intp new_size)
}
if (NPY_UNLIKELY(buffer->pw == NULL)) {
- buffer->pw = malloc(new_size * sizeof(npy_intp));
- } else {
- buffer->pw = realloc(buffer->pw, new_size * sizeof(npy_intp));
+ buffer->pw = (npy_intp *)malloc(new_size * sizeof(npy_intp));
+ }
+ else {
+ buffer->pw =
+ (npy_intp *)realloc(buffer->pw, new_size * sizeof(npy_intp));
}
buffer->size = new_size;
if (NPY_UNLIKELY(buffer->pw == NULL)) {
return -NPY_ENOMEM;
- } else {
+ }
+ else {
return 0;
}
}
@@ -96,56 +98,44 @@ resize_buffer_intp(buffer_intp *buffer, npy_intp new_size)
*****************************************************************************
*/
-
-/**begin repeat
- *
- * #TYPE = BOOL, BYTE, UBYTE, SHORT, USHORT, INT, UINT, LONG, ULONG,
- * LONGLONG, ULONGLONG, HALF, FLOAT, DOUBLE, LONGDOUBLE,
- * CFLOAT, CDOUBLE, CLONGDOUBLE, DATETIME, TIMEDELTA#
- * #suff = bool, byte, ubyte, short, ushort, int, uint, long, ulong,
- * longlong, ulonglong, half, float, double, longdouble,
- * cfloat, cdouble, clongdouble, datetime, timedelta#
- * #type = npy_bool, npy_byte, npy_ubyte, npy_short, npy_ushort, npy_int,
- * npy_uint, npy_long, npy_ulong, npy_longlong, npy_ulonglong,
- * npy_ushort, npy_float, npy_double, npy_longdouble, npy_cfloat,
- * npy_cdouble, npy_clongdouble, npy_datetime, npy_timedelta#
- */
-
-
-typedef struct {
- @type@ * pw;
+template <typename Tag>
+struct buffer_ {
+ typename Tag::type *pw;
npy_intp size;
-} buffer_@suff@;
-
+};
+template <typename Tag>
static NPY_INLINE int
-resize_buffer_@suff@(buffer_@suff@ *buffer, npy_intp new_size)
+resize_buffer_(buffer_<Tag> *buffer, npy_intp new_size)
{
+ using type = typename Tag::type;
if (new_size <= buffer->size) {
return 0;
}
if (NPY_UNLIKELY(buffer->pw == NULL)) {
- buffer->pw = malloc(new_size * sizeof(@type@));
- } else {
- buffer->pw = realloc(buffer->pw, new_size * sizeof(@type@));
+ buffer->pw = (type *)malloc(new_size * sizeof(type));
+ }
+ else {
+ buffer->pw = (type *)realloc(buffer->pw, new_size * sizeof(type));
}
buffer->size = new_size;
if (NPY_UNLIKELY(buffer->pw == NULL)) {
return -NPY_ENOMEM;
- } else {
+ }
+ else {
return 0;
}
}
-
+template <typename Tag, typename type>
static npy_intp
-count_run_@suff@(@type@ *arr, npy_intp l, npy_intp num, npy_intp minrun)
+count_run_(type *arr, npy_intp l, npy_intp num, npy_intp minrun)
{
npy_intp sz;
- @type@ vc, *pl, *pi, *pj, *pr;
+ type vc, *pl, *pi, *pj, *pr;
if (NPY_UNLIKELY(num - l == 1)) {
return 1;
@@ -154,15 +144,18 @@ count_run_@suff@(@type@ *arr, npy_intp l, npy_intp num, npy_intp minrun)
pl = arr + l;
/* (not strictly) ascending sequence */
- if (!@TYPE@_LT(*(pl + 1), *pl)) {
- for (pi = pl + 1; pi < arr + num - 1 && !@TYPE@_LT(*(pi + 1), *pi); ++pi) {
+ if (!Tag::less(*(pl + 1), *pl)) {
+ for (pi = pl + 1; pi < arr + num - 1 && !Tag::less(*(pi + 1), *pi);
+ ++pi) {
}
- } else { /* (strictly) descending sequence */
- for (pi = pl + 1; pi < arr + num - 1 && @TYPE@_LT(*(pi + 1), *pi); ++pi) {
+ }
+ else { /* (strictly) descending sequence */
+ for (pi = pl + 1; pi < arr + num - 1 && Tag::less(*(pi + 1), *pi);
+ ++pi) {
}
for (pj = pl, pr = pi; pj < pr; ++pj, --pr) {
- @TYPE@_SWAP(*pj, *pr);
+ std::swap(*pj, *pr);
}
}
@@ -172,7 +165,8 @@ count_run_@suff@(@type@ *arr, npy_intp l, npy_intp num, npy_intp minrun)
if (sz < minrun) {
if (l + minrun < num) {
sz = minrun;
- } else {
+ }
+ else {
sz = num - l;
}
@@ -183,7 +177,7 @@ count_run_@suff@(@type@ *arr, npy_intp l, npy_intp num, npy_intp minrun)
vc = *pi;
pj = pi;
- while (pl < pj && @TYPE@_LT(vc, *(pj - 1))) {
+ while (pl < pj && Tag::less(vc, *(pj - 1))) {
*pj = *(pj - 1);
--pj;
}
@@ -195,43 +189,42 @@ count_run_@suff@(@type@ *arr, npy_intp l, npy_intp num, npy_intp minrun)
return sz;
}
-
/* when the left part of the array (p1) is smaller, copy p1 to buffer
* and merge from left to right
*/
+template <typename Tag, typename type>
static void
-merge_left_@suff@(@type@ *p1, npy_intp l1, @type@ *p2, npy_intp l2,
- @type@ *p3)
+merge_left_(type *p1, npy_intp l1, type *p2, npy_intp l2, type *p3)
{
- @type@ *end = p2 + l2;
- memcpy(p3, p1, sizeof(@type@) * l1);
+ type *end = p2 + l2;
+ memcpy(p3, p1, sizeof(type) * l1);
/* first element must be in p2 otherwise skipped in the caller */
*p1++ = *p2++;
while (p1 < p2 && p2 < end) {
- if (@TYPE@_LT(*p2, *p3)) {
+ if (Tag::less(*p2, *p3)) {
*p1++ = *p2++;
- } else {
+ }
+ else {
*p1++ = *p3++;
}
}
if (p1 != p2) {
- memcpy(p1, p3, sizeof(@type@) * (p2 - p1));
+ memcpy(p1, p3, sizeof(type) * (p2 - p1));
}
}
-
/* when the right part of the array (p2) is smaller, copy p2 to buffer
* and merge from right to left
*/
+template <typename Tag, typename type>
static void
-merge_right_@suff@(@type@ *p1, npy_intp l1, @type@ *p2, npy_intp l2,
- @type@ *p3)
+merge_right_(type *p1, npy_intp l1, type *p2, npy_intp l2, type *p3)
{
npy_intp ofs;
- @type@ *start = p1 - 1;
- memcpy(p3, p2, sizeof(@type@) * l2);
+ type *start = p1 - 1;
+ memcpy(p3, p2, sizeof(type) * l2);
p1 += l1 - 1;
p2 += l2 - 1;
p3 += l2 - 1;
@@ -239,31 +232,32 @@ merge_right_@suff@(@type@ *p1, npy_intp l1, @type@ *p2, npy_intp l2,
*p2-- = *p1--;
while (p1 < p2 && start < p1) {
- if (@TYPE@_LT(*p3, *p1)) {
+ if (Tag::less(*p3, *p1)) {
*p2-- = *p1--;
- } else {
+ }
+ else {
*p2-- = *p3--;
}
}
if (p1 != p2) {
ofs = p2 - start;
- memcpy(start + 1, p3 - ofs + 1, sizeof(@type@) * ofs);
+ memcpy(start + 1, p3 - ofs + 1, sizeof(type) * ofs);
}
}
-
/* Note: the naming convention of gallop functions are different from that of
* CPython. For example, here gallop_right means gallop from left toward right,
* whereas in CPython gallop_right means gallop
* and find the right most element among equal elements
*/
+template <typename Tag, typename type>
static npy_intp
-gallop_right_@suff@(const @type@ *arr, const npy_intp size, const @type@ key)
+gallop_right_(const type *arr, const npy_intp size, const type key)
{
npy_intp last_ofs, ofs, m;
- if (@TYPE@_LT(key, arr[0])) {
+ if (Tag::less(key, arr[0])) {
return 0;
}
@@ -276,9 +270,10 @@ gallop_right_@suff@(const @type@ *arr, const npy_intp size, const @type@ key)
break;
}
- if (@TYPE@_LT(key, arr[ofs])) {
+ if (Tag::less(key, arr[ofs])) {
break;
- } else {
+ }
+ else {
last_ofs = ofs;
/* ofs = 1, 3, 7, 15... */
ofs = (ofs << 1) + 1;
@@ -289,9 +284,10 @@ gallop_right_@suff@(const @type@ *arr, const npy_intp size, const @type@ key)
while (last_ofs + 1 < ofs) {
m = last_ofs + ((ofs - last_ofs) >> 1);
- if (@TYPE@_LT(key, arr[m])) {
+ if (Tag::less(key, arr[m])) {
ofs = m;
- } else {
+ }
+ else {
last_ofs = m;
}
}
@@ -300,13 +296,13 @@ gallop_right_@suff@(const @type@ *arr, const npy_intp size, const @type@ key)
return ofs;
}
-
+template <typename Tag, typename type>
static npy_intp
-gallop_left_@suff@(const @type@ *arr, const npy_intp size, const @type@ key)
+gallop_left_(const type *arr, const npy_intp size, const type key)
{
npy_intp last_ofs, ofs, l, m, r;
- if (@TYPE@_LT(arr[size - 1], key)) {
+ if (Tag::less(arr[size - 1], key)) {
return size;
}
@@ -319,9 +315,10 @@ gallop_left_@suff@(const @type@ *arr, const npy_intp size, const @type@ key)
break;
}
- if (@TYPE@_LT(arr[size - ofs - 1], key)) {
+ if (Tag::less(arr[size - ofs - 1], key)) {
break;
- } else {
+ }
+ else {
last_ofs = ofs;
ofs = (ofs << 1) + 1;
}
@@ -334,9 +331,10 @@ gallop_left_@suff@(const @type@ *arr, const npy_intp size, const @type@ key)
while (l + 1 < r) {
m = l + ((r - l) >> 1);
- if (@TYPE@_LT(arr[m], key)) {
+ if (Tag::less(arr[m], key)) {
l = m;
- } else {
+ }
+ else {
r = m;
}
}
@@ -345,14 +343,13 @@ gallop_left_@suff@(const @type@ *arr, const npy_intp size, const @type@ key)
return r;
}
-
+template <typename Tag, typename type>
static int
-merge_at_@suff@(@type@ *arr, const run *stack, const npy_intp at,
- buffer_@suff@ *buffer)
+merge_at_(type *arr, const run *stack, const npy_intp at, buffer_<Tag> *buffer)
{
int ret;
npy_intp s1, l1, s2, l2, k;
- @type@ *p1, *p2;
+ type *p1, *p2;
s1 = stack[at].s;
l1 = stack[at].l;
s2 = stack[at + 1].s;
@@ -361,7 +358,7 @@ merge_at_@suff@(@type@ *arr, const run *stack, const npy_intp at,
* if try to comment this out for debugging purpose, remember
* in the merging process the first element is skipped
*/
- k = gallop_right_@suff@(arr + s1, l1, arr[s2]);
+ k = gallop_right_<Tag>(arr + s1, l1, arr[s2]);
if (l1 == k) {
/* already sorted */
@@ -372,29 +369,33 @@ merge_at_@suff@(@type@ *arr, const run *stack, const npy_intp at,
l1 -= k;
p2 = arr + s2;
/* arr[s2-1] belongs to arr[s2+l2] */
- l2 = gallop_left_@suff@(arr + s2, l2, arr[s2 - 1]);
+ l2 = gallop_left_<Tag>(arr + s2, l2, arr[s2 - 1]);
if (l2 < l1) {
- ret = resize_buffer_@suff@(buffer, l2);
+ ret = resize_buffer_<Tag>(buffer, l2);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
- merge_right_@suff@(p1, l1, p2, l2, buffer->pw);
- } else {
- ret = resize_buffer_@suff@(buffer, l1);
+ merge_right_<Tag>(p1, l1, p2, l2, buffer->pw);
+ }
+ else {
+ ret = resize_buffer_<Tag>(buffer, l1);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
- merge_left_@suff@(p1, l1, p2, l2, buffer->pw);
+ merge_left_<Tag>(p1, l1, p2, l2, buffer->pw);
}
return 0;
}
-
+template <typename Tag, typename type>
static int
-try_collapse_@suff@(@type@ *arr, run *stack, npy_intp *stack_ptr,
- buffer_@suff@ *buffer)
+try_collapse_(type *arr, run *stack, npy_intp *stack_ptr, buffer_<Tag> *buffer)
{
int ret;
npy_intp A, B, C, top;
@@ -405,33 +406,42 @@ try_collapse_@suff@(@type@ *arr, run *stack, npy_intp *stack_ptr,
C = stack[top - 1].l;
if ((2 < top && stack[top - 3].l <= B + C) ||
- (3 < top && stack[top - 4].l <= stack[top - 3].l + B)) {
+ (3 < top && stack[top - 4].l <= stack[top - 3].l + B)) {
A = stack[top - 3].l;
if (A <= C) {
- ret = merge_at_@suff@(arr, stack, top - 3, buffer);
+ ret = merge_at_<Tag>(arr, stack, top - 3, buffer);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 3].l += B;
stack[top - 2] = stack[top - 1];
--top;
- } else {
- ret = merge_at_@suff@(arr, stack, top - 2, buffer);
+ }
+ else {
+ ret = merge_at_<Tag>(arr, stack, top - 2, buffer);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 2].l += C;
--top;
}
- } else if (1 < top && B <= C) {
- ret = merge_at_@suff@(arr, stack, top - 2, buffer);
+ }
+ else if (1 < top && B <= C) {
+ ret = merge_at_<Tag>(arr, stack, top - 2, buffer);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 2].l += C;
--top;
- } else {
+ }
+ else {
break;
}
}
@@ -440,26 +450,32 @@ try_collapse_@suff@(@type@ *arr, run *stack, npy_intp *stack_ptr,
return 0;
}
+template <typename Tag, typename type>
static int
-force_collapse_@suff@(@type@ *arr, run *stack, npy_intp *stack_ptr,
- buffer_@suff@ *buffer)
+force_collapse_(type *arr, run *stack, npy_intp *stack_ptr,
+ buffer_<Tag> *buffer)
{
int ret;
npy_intp top = *stack_ptr;
while (2 < top) {
if (stack[top - 3].l <= stack[top - 1].l) {
- ret = merge_at_@suff@(arr, stack, top - 3, buffer);
+ ret = merge_at_<Tag>(arr, stack, top - 3, buffer);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 3].l += stack[top - 2].l;
stack[top - 2] = stack[top - 1];
--top;
- } else {
- ret = merge_at_@suff@(arr, stack, top - 2, buffer);
+ }
+ else {
+ ret = merge_at_<Tag>(arr, stack, top - 2, buffer);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 2].l += stack[top - 1].l;
--top;
@@ -467,21 +483,24 @@ force_collapse_@suff@(@type@ *arr, run *stack, npy_intp *stack_ptr,
}
if (1 < top) {
- ret = merge_at_@suff@(arr, stack, top - 2, buffer);
+ ret = merge_at_<Tag>(arr, stack, top - 2, buffer);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
}
return 0;
}
-
-NPY_NO_EXPORT int
-timsort_@suff@(void *start, npy_intp num, void *NPY_UNUSED(varr))
+template <typename Tag>
+static int
+timsort_(void *start, npy_intp num)
{
+ using type = typename Tag::type;
int ret;
npy_intp l, n, stack_ptr, minrun;
- buffer_@suff@ buffer;
+ buffer_<Tag> buffer;
run stack[TIMSORT_STACK_SIZE];
buffer.pw = NULL;
buffer.size = 0;
@@ -489,20 +508,24 @@ timsort_@suff@(void *start, npy_intp num, void *NPY_UNUSED(varr))
minrun = compute_min_run(num);
for (l = 0; l < num;) {
- n = count_run_@suff@(start, l, num, minrun);
+ n = count_run_<Tag>((type *)start, l, num, minrun);
stack[stack_ptr].s = l;
stack[stack_ptr].l = n;
++stack_ptr;
- ret = try_collapse_@suff@(start, stack, &stack_ptr, &buffer);
+ ret = try_collapse_<Tag>((type *)start, stack, &stack_ptr, &buffer);
- if (NPY_UNLIKELY(ret < 0)) { goto cleanup; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ goto cleanup;
+ }
l += n;
}
- ret = force_collapse_@suff@(start, stack, &stack_ptr, &buffer);
+ ret = force_collapse_<Tag>((type *)start, stack, &stack_ptr, &buffer);
- if (NPY_UNLIKELY(ret < 0)) { goto cleanup; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ goto cleanup;
+ }
ret = 0;
cleanup:
@@ -512,16 +535,15 @@ cleanup:
return ret;
}
-
/* argsort */
-
+template <typename Tag, typename type>
static npy_intp
-acount_run_@suff@(@type@ *arr, npy_intp *tosort, npy_intp l, npy_intp num,
- npy_intp minrun)
+acount_run_(type *arr, npy_intp *tosort, npy_intp l, npy_intp num,
+ npy_intp minrun)
{
npy_intp sz;
- @type@ vc;
+ type vc;
npy_intp vi;
npy_intp *pl, *pi, *pj, *pr;
@@ -532,17 +554,20 @@ acount_run_@suff@(@type@ *arr, npy_intp *tosort, npy_intp l, npy_intp num,
pl = tosort + l;
/* (not strictly) ascending sequence */
- if (!@TYPE@_LT(arr[*(pl + 1)], arr[*pl])) {
- for (pi = pl + 1; pi < tosort + num - 1
- && !@TYPE@_LT(arr[*(pi + 1)], arr[*pi]); ++pi) {
+ if (!Tag::less(arr[*(pl + 1)], arr[*pl])) {
+ for (pi = pl + 1;
+ pi < tosort + num - 1 && !Tag::less(arr[*(pi + 1)], arr[*pi]);
+ ++pi) {
}
- } else { /* (strictly) descending sequence */
- for (pi = pl + 1; pi < tosort + num - 1
- && @TYPE@_LT(arr[*(pi + 1)], arr[*pi]); ++pi) {
+ }
+ else { /* (strictly) descending sequence */
+ for (pi = pl + 1;
+ pi < tosort + num - 1 && Tag::less(arr[*(pi + 1)], arr[*pi]);
+ ++pi) {
}
for (pj = pl, pr = pi; pj < pr; ++pj, --pr) {
- INTP_SWAP(*pj, *pr);
+ std::swap(*pj, *pr);
}
}
@@ -552,7 +577,8 @@ acount_run_@suff@(@type@ *arr, npy_intp *tosort, npy_intp l, npy_intp num,
if (sz < minrun) {
if (l + minrun < num) {
sz = minrun;
- } else {
+ }
+ else {
sz = num - l;
}
@@ -564,7 +590,7 @@ acount_run_@suff@(@type@ *arr, npy_intp *tosort, npy_intp l, npy_intp num,
vc = arr[*pi];
pj = pi;
- while (pl < pj && @TYPE@_LT(vc, arr[*(pj - 1)])) {
+ while (pl < pj && Tag::less(vc, arr[*(pj - 1)])) {
*pj = *(pj - 1);
--pj;
}
@@ -576,14 +602,14 @@ acount_run_@suff@(@type@ *arr, npy_intp *tosort, npy_intp l, npy_intp num,
return sz;
}
-
+template <typename Tag, typename type>
static npy_intp
-agallop_right_@suff@(const @type@ *arr, const npy_intp *tosort,
- const npy_intp size, const @type@ key)
+agallop_right_(const type *arr, const npy_intp *tosort, const npy_intp size,
+ const type key)
{
npy_intp last_ofs, ofs, m;
- if (@TYPE@_LT(key, arr[tosort[0]])) {
+ if (Tag::less(key, arr[tosort[0]])) {
return 0;
}
@@ -596,9 +622,10 @@ agallop_right_@suff@(const @type@ *arr, const npy_intp *tosort,
break;
}
- if (@TYPE@_LT(key, arr[tosort[ofs]])) {
+ if (Tag::less(key, arr[tosort[ofs]])) {
break;
- } else {
+ }
+ else {
last_ofs = ofs;
/* ofs = 1, 3, 7, 15... */
ofs = (ofs << 1) + 1;
@@ -609,9 +636,10 @@ agallop_right_@suff@(const @type@ *arr, const npy_intp *tosort,
while (last_ofs + 1 < ofs) {
m = last_ofs + ((ofs - last_ofs) >> 1);
- if (@TYPE@_LT(key, arr[tosort[m]])) {
+ if (Tag::less(key, arr[tosort[m]])) {
ofs = m;
- } else {
+ }
+ else {
last_ofs = m;
}
}
@@ -620,15 +648,14 @@ agallop_right_@suff@(const @type@ *arr, const npy_intp *tosort,
return ofs;
}
-
-
+template <typename Tag, typename type>
static npy_intp
-agallop_left_@suff@(const @type@ *arr, const npy_intp *tosort,
- const npy_intp size, const @type@ key)
+agallop_left_(const type *arr, const npy_intp *tosort, const npy_intp size,
+ const type key)
{
npy_intp last_ofs, ofs, l, m, r;
- if (@TYPE@_LT(arr[tosort[size - 1]], key)) {
+ if (Tag::less(arr[tosort[size - 1]], key)) {
return size;
}
@@ -641,24 +668,27 @@ agallop_left_@suff@(const @type@ *arr, const npy_intp *tosort,
break;
}
- if (@TYPE@_LT(arr[tosort[size - ofs - 1]], key)) {
+ if (Tag::less(arr[tosort[size - ofs - 1]], key)) {
break;
- } else {
+ }
+ else {
last_ofs = ofs;
ofs = (ofs << 1) + 1;
}
}
- /* now that arr[tosort[size-ofs-1]] < key <= arr[tosort[size-last_ofs-1]] */
+ /* now that arr[tosort[size-ofs-1]] < key <= arr[tosort[size-last_ofs-1]]
+ */
l = size - ofs - 1;
r = size - last_ofs - 1;
while (l + 1 < r) {
m = l + ((r - l) >> 1);
- if (@TYPE@_LT(arr[tosort[m]], key)) {
+ if (Tag::less(arr[tosort[m]], key)) {
l = m;
- } else {
+ }
+ else {
r = m;
}
}
@@ -667,11 +697,10 @@ agallop_left_@suff@(const @type@ *arr, const npy_intp *tosort,
return r;
}
-
+template <typename Tag, typename type>
static void
-amerge_left_@suff@(@type@ *arr, npy_intp *p1, npy_intp l1, npy_intp *p2,
- npy_intp l2,
- npy_intp *p3)
+amerge_left_(type *arr, npy_intp *p1, npy_intp l1, npy_intp *p2, npy_intp l2,
+ npy_intp *p3)
{
npy_intp *end = p2 + l2;
memcpy(p3, p1, sizeof(npy_intp) * l1);
@@ -679,9 +708,10 @@ amerge_left_@suff@(@type@ *arr, npy_intp *p1, npy_intp l1, npy_intp *p2,
*p1++ = *p2++;
while (p1 < p2 && p2 < end) {
- if (@TYPE@_LT(arr[*p2], arr[*p3])) {
+ if (Tag::less(arr[*p2], arr[*p3])) {
*p1++ = *p2++;
- } else {
+ }
+ else {
*p1++ = *p3++;
}
}
@@ -691,11 +721,10 @@ amerge_left_@suff@(@type@ *arr, npy_intp *p1, npy_intp l1, npy_intp *p2,
}
}
-
+template <typename Tag, typename type>
static void
-amerge_right_@suff@(@type@ *arr, npy_intp* p1, npy_intp l1, npy_intp *p2,
- npy_intp l2,
- npy_intp *p3)
+amerge_right_(type *arr, npy_intp *p1, npy_intp l1, npy_intp *p2, npy_intp l2,
+ npy_intp *p3)
{
npy_intp ofs;
npy_intp *start = p1 - 1;
@@ -707,9 +736,10 @@ amerge_right_@suff@(@type@ *arr, npy_intp* p1, npy_intp l1, npy_intp *p2,
*p2-- = *p1--;
while (p1 < p2 && start < p1) {
- if (@TYPE@_LT(arr[*p3], arr[*p1])) {
+ if (Tag::less(arr[*p3], arr[*p1])) {
*p2-- = *p1--;
- } else {
+ }
+ else {
*p2-- = *p3--;
}
}
@@ -720,11 +750,10 @@ amerge_right_@suff@(@type@ *arr, npy_intp* p1, npy_intp l1, npy_intp *p2,
}
}
-
+template <typename Tag, typename type>
static int
-amerge_at_@suff@(@type@ *arr, npy_intp *tosort, const run *stack,
- const npy_intp at,
- buffer_intp *buffer)
+amerge_at_(type *arr, npy_intp *tosort, const run *stack, const npy_intp at,
+ buffer_intp *buffer)
{
int ret;
npy_intp s1, l1, s2, l2, k;
@@ -734,7 +763,7 @@ amerge_at_@suff@(@type@ *arr, npy_intp *tosort, const run *stack,
s2 = stack[at + 1].s;
l2 = stack[at + 1].l;
/* tosort[s2] belongs to tosort[s1+k] */
- k = agallop_right_@suff@(arr, tosort + s1, l1, arr[tosort[s2]]);
+ k = agallop_right_<Tag>(arr, tosort + s1, l1, arr[tosort[s2]]);
if (l1 == k) {
/* already sorted */
@@ -745,30 +774,34 @@ amerge_at_@suff@(@type@ *arr, npy_intp *tosort, const run *stack,
l1 -= k;
p2 = tosort + s2;
/* tosort[s2-1] belongs to tosort[s2+l2] */
- l2 = agallop_left_@suff@(arr, tosort + s2, l2, arr[tosort[s2 - 1]]);
+ l2 = agallop_left_<Tag>(arr, tosort + s2, l2, arr[tosort[s2 - 1]]);
if (l2 < l1) {
ret = resize_buffer_intp(buffer, l2);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
- amerge_right_@suff@(arr, p1, l1, p2, l2, buffer->pw);
- } else {
+ amerge_right_<Tag>(arr, p1, l1, p2, l2, buffer->pw);
+ }
+ else {
ret = resize_buffer_intp(buffer, l1);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
- amerge_left_@suff@(arr, p1, l1, p2, l2, buffer->pw);
+ amerge_left_<Tag>(arr, p1, l1, p2, l2, buffer->pw);
}
return 0;
}
-
+template <typename Tag, typename type>
static int
-atry_collapse_@suff@(@type@ *arr, npy_intp *tosort, run *stack,
- npy_intp *stack_ptr,
- buffer_intp *buffer)
+atry_collapse_(type *arr, npy_intp *tosort, run *stack, npy_intp *stack_ptr,
+ buffer_intp *buffer)
{
int ret;
npy_intp A, B, C, top;
@@ -779,33 +812,42 @@ atry_collapse_@suff@(@type@ *arr, npy_intp *tosort, run *stack,
C = stack[top - 1].l;
if ((2 < top && stack[top - 3].l <= B + C) ||
- (3 < top && stack[top - 4].l <= stack[top - 3].l + B)) {
+ (3 < top && stack[top - 4].l <= stack[top - 3].l + B)) {
A = stack[top - 3].l;
if (A <= C) {
- ret = amerge_at_@suff@(arr, tosort, stack, top - 3, buffer);
+ ret = amerge_at_<Tag>(arr, tosort, stack, top - 3, buffer);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 3].l += B;
stack[top - 2] = stack[top - 1];
--top;
- } else {
- ret = amerge_at_@suff@(arr, tosort, stack, top - 2, buffer);
+ }
+ else {
+ ret = amerge_at_<Tag>(arr, tosort, stack, top - 2, buffer);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 2].l += C;
--top;
}
- } else if (1 < top && B <= C) {
- ret = amerge_at_@suff@(arr, tosort, stack, top - 2, buffer);
+ }
+ else if (1 < top && B <= C) {
+ ret = amerge_at_<Tag>(arr, tosort, stack, top - 2, buffer);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 2].l += C;
--top;
- } else {
+ }
+ else {
break;
}
}
@@ -814,28 +856,32 @@ atry_collapse_@suff@(@type@ *arr, npy_intp *tosort, run *stack,
return 0;
}
-
+template <typename Tag, typename type>
static int
-aforce_collapse_@suff@(@type@ *arr, npy_intp *tosort, run *stack,
- npy_intp *stack_ptr,
- buffer_intp *buffer)
+aforce_collapse_(type *arr, npy_intp *tosort, run *stack, npy_intp *stack_ptr,
+ buffer_intp *buffer)
{
int ret;
npy_intp top = *stack_ptr;
while (2 < top) {
if (stack[top - 3].l <= stack[top - 1].l) {
- ret = amerge_at_@suff@(arr, tosort, stack, top - 3, buffer);
+ ret = amerge_at_<Tag>(arr, tosort, stack, top - 3, buffer);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 3].l += stack[top - 2].l;
stack[top - 2] = stack[top - 1];
--top;
- } else {
- ret = amerge_at_@suff@(arr, tosort, stack, top - 2, buffer);
+ }
+ else {
+ ret = amerge_at_<Tag>(arr, tosort, stack, top - 2, buffer);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 2].l += stack[top - 1].l;
--top;
@@ -843,19 +889,21 @@ aforce_collapse_@suff@(@type@ *arr, npy_intp *tosort, run *stack,
}
if (1 < top) {
- ret = amerge_at_@suff@(arr, tosort, stack, top - 2, buffer);
+ ret = amerge_at_<Tag>(arr, tosort, stack, top - 2, buffer);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
}
return 0;
}
-
-NPY_NO_EXPORT int
-atimsort_@suff@(void *v, npy_intp *tosort, npy_intp num,
- void *NPY_UNUSED(varr))
+template <typename Tag>
+static int
+atimsort_(void *v, npy_intp *tosort, npy_intp num)
{
+ using type = typename Tag::type;
int ret;
npy_intp l, n, stack_ptr, minrun;
buffer_intp buffer;
@@ -866,20 +914,25 @@ atimsort_@suff@(void *v, npy_intp *tosort, npy_intp num,
minrun = compute_min_run(num);
for (l = 0; l < num;) {
- n = acount_run_@suff@(v, tosort, l, num, minrun);
+ n = acount_run_<Tag>((type *)v, tosort, l, num, minrun);
stack[stack_ptr].s = l;
stack[stack_ptr].l = n;
++stack_ptr;
- ret = atry_collapse_@suff@(v, tosort, stack, &stack_ptr, &buffer);
+ ret = atry_collapse_<Tag>((type *)v, tosort, stack, &stack_ptr,
+ &buffer);
- if (NPY_UNLIKELY(ret < 0)) { goto cleanup; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ goto cleanup;
+ }
l += n;
}
- ret = aforce_collapse_@suff@(v, tosort, stack, &stack_ptr, &buffer);
+ ret = aforce_collapse_<Tag>((type *)v, tosort, stack, &stack_ptr, &buffer);
- if (NPY_UNLIKELY(ret < 0)) { goto cleanup; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ goto cleanup;
+ }
ret = 0;
cleanup:
@@ -891,18 +944,15 @@ cleanup:
return ret;
}
-/**end repeat**/
-
-
-
/* For string sorts and generic sort, element comparisons are very expensive,
- * and the time cost of insertion sort (involves N**2 comparison) clearly hurts.
- * Implementing binary insertion sort and probably gallop mode during merging process
- * can hopefully boost the performance. Here as a temporary workaround we use shorter
- * run length to reduce the cost of insertion sort.
+ * and the time cost of insertion sort (involves N**2 comparison) clearly
+ * hurts. Implementing binary insertion sort and probably gallop mode during
+ * merging process can hopefully boost the performance. Here as a temporary
+ * workaround we use shorter run length to reduce the cost of insertion sort.
*/
-static npy_intp compute_min_run_short(npy_intp num)
+static npy_intp
+compute_min_run_short(npy_intp num)
{
npy_intp r = 0;
@@ -920,51 +970,47 @@ static npy_intp compute_min_run_short(npy_intp num)
*****************************************************************************
*/
-
-/**begin repeat
- *
- * #TYPE = STRING, UNICODE#
- * #suff = string, unicode#
- * #type = npy_char, npy_ucs4#
- */
-
-
-typedef struct {
- @type@ * pw;
+template <typename Tag>
+struct string_buffer_ {
+ typename Tag::type *pw;
npy_intp size;
size_t len;
-} buffer_@suff@;
-
+};
+template <typename Tag>
static NPY_INLINE int
-resize_buffer_@suff@(buffer_@suff@ *buffer, npy_intp new_size)
+resize_buffer_(string_buffer_<Tag> *buffer, npy_intp new_size)
{
+ using type = typename Tag::type;
if (new_size <= buffer->size) {
return 0;
}
if (NPY_UNLIKELY(buffer->pw == NULL)) {
- buffer->pw = malloc(sizeof(@type@) * new_size * buffer->len);
- } else {
- buffer->pw = realloc(buffer->pw, sizeof(@type@) * new_size * buffer->len);
+ buffer->pw = (type *)malloc(sizeof(type) * new_size * buffer->len);
+ }
+ else {
+ buffer->pw = (type *)realloc(buffer->pw,
+ sizeof(type) * new_size * buffer->len);
}
buffer->size = new_size;
if (NPY_UNLIKELY(buffer->pw == NULL)) {
return -NPY_ENOMEM;
- } else {
+ }
+ else {
return 0;
}
}
-
+template <typename Tag, typename type>
static npy_intp
-count_run_@suff@(@type@ *arr, npy_intp l, npy_intp num, npy_intp minrun,
- @type@ *vp, size_t len)
+count_run_(type *arr, npy_intp l, npy_intp num, npy_intp minrun, type *vp,
+ size_t len)
{
npy_intp sz;
- @type@ *pl, *pi, *pj, *pr;
+ type *pl, *pi, *pj, *pr;
if (NPY_UNLIKELY(num - l == 1)) {
return 1;
@@ -973,17 +1019,20 @@ count_run_@suff@(@type@ *arr, npy_intp l, npy_intp num, npy_intp minrun,
pl = arr + l * len;
/* (not strictly) ascending sequence */
- if (!@TYPE@_LT(pl + len, pl, len)) {
- for (pi = pl + len; pi < arr + (num - 1) * len
- && !@TYPE@_LT(pi + len, pi, len); pi += len) {
+ if (!Tag::less(pl + len, pl, len)) {
+ for (pi = pl + len;
+ pi < arr + (num - 1) * len && !Tag::less(pi + len, pi, len);
+ pi += len) {
}
- } else { /* (strictly) descending sequence */
- for (pi = pl + len; pi < arr + (num - 1) * len
- && @TYPE@_LT(pi + len, pi, len); pi += len) {
+ }
+ else { /* (strictly) descending sequence */
+ for (pi = pl + len;
+ pi < arr + (num - 1) * len && Tag::less(pi + len, pi, len);
+ pi += len) {
}
for (pj = pl, pr = pi; pj < pr; pj += len, pr -= len) {
- @TYPE@_SWAP(pj, pr, len);
+ Tag::swap(pj, pr, len);
}
}
@@ -993,7 +1042,8 @@ count_run_@suff@(@type@ *arr, npy_intp l, npy_intp num, npy_intp minrun,
if (sz < minrun) {
if (l + minrun < num) {
sz = minrun;
- } else {
+ }
+ else {
sz = num - l;
}
@@ -1001,29 +1051,29 @@ count_run_@suff@(@type@ *arr, npy_intp l, npy_intp num, npy_intp minrun,
/* insertion sort */
for (; pi < pr; pi += len) {
- @TYPE@_COPY(vp, pi, len);
+ Tag::copy(vp, pi, len);
pj = pi;
- while (pl < pj && @TYPE@_LT(vp, pj - len, len)) {
- @TYPE@_COPY(pj, pj - len, len);
+ while (pl < pj && Tag::less(vp, pj - len, len)) {
+ Tag::copy(pj, pj - len, len);
pj -= len;
}
- @TYPE@_COPY(pj, vp, len);
+ Tag::copy(pj, vp, len);
}
}
return sz;
}
-
+template <typename Tag>
static npy_intp
-gallop_right_@suff@(const @type@ *arr, const npy_intp size,
- const @type@ *key, size_t len)
+gallop_right_(const typename Tag::type *arr, const npy_intp size,
+ const typename Tag::type *key, size_t len)
{
npy_intp last_ofs, ofs, m;
- if (@TYPE@_LT(key, arr, len)) {
+ if (Tag::less(key, arr, len)) {
return 0;
}
@@ -1036,9 +1086,10 @@ gallop_right_@suff@(const @type@ *arr, const npy_intp size,
break;
}
- if (@TYPE@_LT(key, arr + ofs * len, len)) {
+ if (Tag::less(key, arr + ofs * len, len)) {
break;
- } else {
+ }
+ else {
last_ofs = ofs;
/* ofs = 1, 3, 7, 15... */
ofs = (ofs << 1) + 1;
@@ -1049,9 +1100,10 @@ gallop_right_@suff@(const @type@ *arr, const npy_intp size,
while (last_ofs + 1 < ofs) {
m = last_ofs + ((ofs - last_ofs) >> 1);
- if (@TYPE@_LT(key, arr + m * len, len)) {
+ if (Tag::less(key, arr + m * len, len)) {
ofs = m;
- } else {
+ }
+ else {
last_ofs = m;
}
}
@@ -1060,15 +1112,14 @@ gallop_right_@suff@(const @type@ *arr, const npy_intp size,
return ofs;
}
-
-
+template <typename Tag>
static npy_intp
-gallop_left_@suff@(const @type@ *arr, const npy_intp size, const @type@ *key,
- size_t len)
+gallop_left_(const typename Tag::type *arr, const npy_intp size,
+ const typename Tag::type *key, size_t len)
{
npy_intp last_ofs, ofs, l, m, r;
- if (@TYPE@_LT(arr + (size - 1) * len, key, len)) {
+ if (Tag::less(arr + (size - 1) * len, key, len)) {
return size;
}
@@ -1081,9 +1132,10 @@ gallop_left_@suff@(const @type@ *arr, const npy_intp size, const @type@ *key,
break;
}
- if (@TYPE@_LT(arr + (size - ofs - 1) * len, key, len)) {
+ if (Tag::less(arr + (size - ofs - 1) * len, key, len)) {
break;
- } else {
+ }
+ else {
last_ofs = ofs;
ofs = (ofs << 1) + 1;
}
@@ -1096,9 +1148,10 @@ gallop_left_@suff@(const @type@ *arr, const npy_intp size, const @type@ *key,
while (l + 1 < r) {
m = l + ((r - l) >> 1);
- if (@TYPE@_LT(arr + m * len, key, len)) {
+ if (Tag::less(arr + m * len, key, len)) {
l = m;
- } else {
+ }
+ else {
r = m;
}
}
@@ -1107,58 +1160,61 @@ gallop_left_@suff@(const @type@ *arr, const npy_intp size, const @type@ *key,
return r;
}
-
+template <typename Tag>
static void
-merge_left_@suff@(@type@ *p1, npy_intp l1, @type@ *p2, npy_intp l2,
- @type@ *p3, size_t len)
+merge_left_(typename Tag::type *p1, npy_intp l1, typename Tag::type *p2,
+ npy_intp l2, typename Tag::type *p3, size_t len)
{
- @type@ *end = p2 + l2 * len;
- memcpy(p3, p1, sizeof(@type@) * l1 * len);
+ using type = typename Tag::type;
+ type *end = p2 + l2 * len;
+ memcpy(p3, p1, sizeof(type) * l1 * len);
/* first element must be in p2 otherwise skipped in the caller */
- @TYPE@_COPY(p1, p2, len);
+ Tag::copy(p1, p2, len);
p1 += len;
p2 += len;
while (p1 < p2 && p2 < end) {
- if (@TYPE@_LT(p2, p3, len)) {
- @TYPE@_COPY(p1, p2, len);
+ if (Tag::less(p2, p3, len)) {
+ Tag::copy(p1, p2, len);
p1 += len;
p2 += len;
- } else {
- @TYPE@_COPY(p1, p3, len);
+ }
+ else {
+ Tag::copy(p1, p3, len);
p1 += len;
p3 += len;
}
}
if (p1 != p2) {
- memcpy(p1, p3, sizeof(@type@) * (p2 - p1));
+ memcpy(p1, p3, sizeof(type) * (p2 - p1));
}
}
-
+template <typename Tag, typename type>
static void
-merge_right_@suff@(@type@ *p1, npy_intp l1, @type@ *p2, npy_intp l2,
- @type@ *p3, size_t len)
+merge_right_(type *p1, npy_intp l1, type *p2, npy_intp l2, type *p3,
+ size_t len)
{
npy_intp ofs;
- @type@ *start = p1 - len;
- memcpy(p3, p2, sizeof(@type@) * l2 * len);
+ type *start = p1 - len;
+ memcpy(p3, p2, sizeof(type) * l2 * len);
p1 += (l1 - 1) * len;
p2 += (l2 - 1) * len;
p3 += (l2 - 1) * len;
/* first element must be in p1 otherwise skipped in the caller */
- @TYPE@_COPY(p2, p1, len);
+ Tag::copy(p2, p1, len);
p2 -= len;
p1 -= len;
while (p1 < p2 && start < p1) {
- if (@TYPE@_LT(p3, p1, len)) {
- @TYPE@_COPY(p2, p1, len);
+ if (Tag::less(p3, p1, len)) {
+ Tag::copy(p2, p1, len);
p2 -= len;
p1 -= len;
- } else {
- @TYPE@_COPY(p2, p3, len);
+ }
+ else {
+ Tag::copy(p2, p3, len);
p2 -= len;
p3 -= len;
}
@@ -1166,25 +1222,25 @@ merge_right_@suff@(@type@ *p1, npy_intp l1, @type@ *p2, npy_intp l2,
if (p1 != p2) {
ofs = p2 - start;
- memcpy(start + len, p3 - ofs + len, sizeof(@type@) * ofs);
+ memcpy(start + len, p3 - ofs + len, sizeof(type) * ofs);
}
}
-
+template <typename Tag, typename type>
static int
-merge_at_@suff@(@type@ *arr, const run *stack, const npy_intp at,
- buffer_@suff@ *buffer, size_t len)
+merge_at_(type *arr, const run *stack, const npy_intp at,
+ string_buffer_<Tag> *buffer, size_t len)
{
int ret;
npy_intp s1, l1, s2, l2, k;
- @type@ *p1, *p2;
+ type *p1, *p2;
s1 = stack[at].s;
l1 = stack[at].l;
s2 = stack[at + 1].s;
l2 = stack[at + 1].l;
/* arr[s2] belongs to arr[s1+k] */
- @TYPE@_COPY(buffer->pw, arr + s2 * len, len);
- k = gallop_right_@suff@(arr + s1 * len, l1, buffer->pw, len);
+ Tag::copy(buffer->pw, arr + s2 * len, len);
+ k = gallop_right_<Tag>(arr + s1 * len, l1, buffer->pw, len);
if (l1 == k) {
/* already sorted */
@@ -1195,30 +1251,35 @@ merge_at_@suff@(@type@ *arr, const run *stack, const npy_intp at,
l1 -= k;
p2 = arr + s2 * len;
/* arr[s2-1] belongs to arr[s2+l2] */
- @TYPE@_COPY(buffer->pw, arr + (s2 - 1) * len, len);
- l2 = gallop_left_@suff@(arr + s2 * len, l2, buffer->pw, len);
+ Tag::copy(buffer->pw, arr + (s2 - 1) * len, len);
+ l2 = gallop_left_<Tag>(arr + s2 * len, l2, buffer->pw, len);
if (l2 < l1) {
- ret = resize_buffer_@suff@(buffer, l2);
+ ret = resize_buffer_<Tag>(buffer, l2);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
- merge_right_@suff@(p1, l1, p2, l2, buffer->pw, len);
- } else {
- ret = resize_buffer_@suff@(buffer, l1);
+ merge_right_<Tag>(p1, l1, p2, l2, buffer->pw, len);
+ }
+ else {
+ ret = resize_buffer_<Tag>(buffer, l1);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
- merge_left_@suff@(p1, l1, p2, l2, buffer->pw, len);
+ merge_left_<Tag>(p1, l1, p2, l2, buffer->pw, len);
}
return 0;
}
-
+template <typename Tag, typename type>
static int
-try_collapse_@suff@(@type@ *arr, run *stack, npy_intp *stack_ptr,
- buffer_@suff@ *buffer, size_t len)
+try_collapse_(type *arr, run *stack, npy_intp *stack_ptr,
+ string_buffer_<Tag> *buffer, size_t len)
{
int ret;
npy_intp A, B, C, top;
@@ -1229,33 +1290,42 @@ try_collapse_@suff@(@type@ *arr, run *stack, npy_intp *stack_ptr,
C = stack[top - 1].l;
if ((2 < top && stack[top - 3].l <= B + C) ||
- (3 < top && stack[top - 4].l <= stack[top - 3].l + B)) {
+ (3 < top && stack[top - 4].l <= stack[top - 3].l + B)) {
A = stack[top - 3].l;
if (A <= C) {
- ret = merge_at_@suff@(arr, stack, top - 3, buffer, len);
+ ret = merge_at_<Tag>(arr, stack, top - 3, buffer, len);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 3].l += B;
stack[top - 2] = stack[top - 1];
--top;
- } else {
- ret = merge_at_@suff@(arr, stack, top - 2, buffer, len);
+ }
+ else {
+ ret = merge_at_<Tag>(arr, stack, top - 2, buffer, len);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 2].l += C;
--top;
}
- } else if (1 < top && B <= C) {
- ret = merge_at_@suff@(arr, stack, top - 2, buffer, len);
+ }
+ else if (1 < top && B <= C) {
+ ret = merge_at_<Tag>(arr, stack, top - 2, buffer, len);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 2].l += C;
--top;
- } else {
+ }
+ else {
break;
}
}
@@ -1264,27 +1334,32 @@ try_collapse_@suff@(@type@ *arr, run *stack, npy_intp *stack_ptr,
return 0;
}
-
+template <typename Tag, typename type>
static int
-force_collapse_@suff@(@type@ *arr, run *stack, npy_intp *stack_ptr,
- buffer_@suff@ *buffer, size_t len)
+force_collapse_(type *arr, run *stack, npy_intp *stack_ptr,
+ string_buffer_<Tag> *buffer, size_t len)
{
int ret;
npy_intp top = *stack_ptr;
while (2 < top) {
if (stack[top - 3].l <= stack[top - 1].l) {
- ret = merge_at_@suff@(arr, stack, top - 3, buffer, len);
+ ret = merge_at_<Tag>(arr, stack, top - 3, buffer, len);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 3].l += stack[top - 2].l;
stack[top - 2] = stack[top - 1];
--top;
- } else {
- ret = merge_at_@suff@(arr, stack, top - 2, buffer, len);
+ }
+ else {
+ ret = merge_at_<Tag>(arr, stack, top - 2, buffer, len);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 2].l += stack[top - 1].l;
--top;
@@ -1292,25 +1367,28 @@ force_collapse_@suff@(@type@ *arr, run *stack, npy_intp *stack_ptr,
}
if (1 < top) {
- ret = merge_at_@suff@(arr, stack, top - 2, buffer, len);
+ ret = merge_at_<Tag>(arr, stack, top - 2, buffer, len);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
}
return 0;
}
-
+template <typename Tag>
NPY_NO_EXPORT int
-timsort_@suff@(void *start, npy_intp num, void *varr)
+string_timsort_(void *start, npy_intp num, void *varr)
{
- PyArrayObject *arr = varr;
+ using type = typename Tag::type;
+ PyArrayObject *arr = reinterpret_cast<PyArrayObject *>(varr);
size_t elsize = PyArray_ITEMSIZE(arr);
- size_t len = elsize / sizeof(@type@);
+ size_t len = elsize / sizeof(type);
int ret;
npy_intp l, n, stack_ptr, minrun;
run stack[TIMSORT_STACK_SIZE];
- buffer_@suff@ buffer;
+ string_buffer_<Tag> buffer;
/* Items that have zero size don't make sense to sort */
if (len == 0) {
@@ -1323,26 +1401,33 @@ timsort_@suff@(void *start, npy_intp num, void *varr)
stack_ptr = 0;
minrun = compute_min_run_short(num);
/* used for insertion sort and gallop key */
- ret = resize_buffer_@suff@(&buffer, 1);
+ ret = resize_buffer_<Tag>(&buffer, 1);
- if (NPY_UNLIKELY(ret < 0)) { goto cleanup; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ goto cleanup;
+ }
for (l = 0; l < num;) {
- n = count_run_@suff@(start, l, num, minrun, buffer.pw, len);
+ n = count_run_<Tag>((type *)start, l, num, minrun, buffer.pw, len);
/* both s and l are scaled by len */
stack[stack_ptr].s = l;
stack[stack_ptr].l = n;
++stack_ptr;
- ret = try_collapse_@suff@(start, stack, &stack_ptr, &buffer, len);
+ ret = try_collapse_<Tag>((type *)start, stack, &stack_ptr, &buffer,
+ len);
- if (NPY_UNLIKELY(ret < 0)) { goto cleanup; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ goto cleanup;
+ }
l += n;
}
- ret = force_collapse_@suff@(start, stack, &stack_ptr, &buffer, len);
+ ret = force_collapse_<Tag>((type *)start, stack, &stack_ptr, &buffer, len);
- if (NPY_UNLIKELY(ret < 0)) { goto cleanup; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ goto cleanup;
+ }
ret = 0;
@@ -1353,13 +1438,12 @@ cleanup:
return ret;
}
-
/* argsort */
-
+template <typename Tag, typename type>
static npy_intp
-acount_run_@suff@(@type@ *arr, npy_intp *tosort, npy_intp l, npy_intp num,
- npy_intp minrun, size_t len)
+acount_run_(type *arr, npy_intp *tosort, npy_intp l, npy_intp num,
+ npy_intp minrun, size_t len)
{
npy_intp sz;
npy_intp vi;
@@ -1372,17 +1456,22 @@ acount_run_@suff@(@type@ *arr, npy_intp *tosort, npy_intp l, npy_intp num,
pl = tosort + l;
/* (not strictly) ascending sequence */
- if (!@TYPE@_LT(arr + (*(pl + 1)) * len, arr + (*pl) * len, len)) {
- for (pi = pl + 1; pi < tosort + num - 1
- && !@TYPE@_LT(arr + (*(pi + 1)) * len, arr + (*pi) * len, len); ++pi) {
+ if (!Tag::less(arr + (*(pl + 1)) * len, arr + (*pl) * len, len)) {
+ for (pi = pl + 1;
+ pi < tosort + num - 1 &&
+ !Tag::less(arr + (*(pi + 1)) * len, arr + (*pi) * len, len);
+ ++pi) {
}
- } else { /* (strictly) descending sequence */
- for (pi = pl + 1; pi < tosort + num - 1
- && @TYPE@_LT(arr + (*(pi + 1)) * len, arr + (*pi) * len, len); ++pi) {
+ }
+ else { /* (strictly) descending sequence */
+ for (pi = pl + 1;
+ pi < tosort + num - 1 &&
+ Tag::less(arr + (*(pi + 1)) * len, arr + (*pi) * len, len);
+ ++pi) {
}
for (pj = pl, pr = pi; pj < pr; ++pj, --pr) {
- INTP_SWAP(*pj, *pr);
+ std::swap(*pj, *pr);
}
}
@@ -1392,7 +1481,8 @@ acount_run_@suff@(@type@ *arr, npy_intp *tosort, npy_intp l, npy_intp num,
if (sz < minrun) {
if (l + minrun < num) {
sz = minrun;
- } else {
+ }
+ else {
sz = num - l;
}
@@ -1403,7 +1493,8 @@ acount_run_@suff@(@type@ *arr, npy_intp *tosort, npy_intp l, npy_intp num,
vi = *pi;
pj = pi;
- while (pl < pj && @TYPE@_LT(arr + vi * len, arr + (*(pj - 1)) * len, len)) {
+ while (pl < pj &&
+ Tag::less(arr + vi * len, arr + (*(pj - 1)) * len, len)) {
*pj = *(pj - 1);
--pj;
}
@@ -1415,14 +1506,14 @@ acount_run_@suff@(@type@ *arr, npy_intp *tosort, npy_intp l, npy_intp num,
return sz;
}
-
+template <typename Tag, typename type>
static npy_intp
-agallop_left_@suff@(const @type@ *arr, const npy_intp *tosort,
- const npy_intp size, const @type@ *key, size_t len)
+agallop_left_(const type *arr, const npy_intp *tosort, const npy_intp size,
+ const type *key, size_t len)
{
npy_intp last_ofs, ofs, l, m, r;
- if (@TYPE@_LT(arr + tosort[size - 1] * len, key, len)) {
+ if (Tag::less(arr + tosort[size - 1] * len, key, len)) {
return size;
}
@@ -1435,24 +1526,27 @@ agallop_left_@suff@(const @type@ *arr, const npy_intp *tosort,
break;
}
- if (@TYPE@_LT(arr + tosort[size - ofs - 1] * len, key, len)) {
+ if (Tag::less(arr + tosort[size - ofs - 1] * len, key, len)) {
break;
- } else {
+ }
+ else {
last_ofs = ofs;
ofs = (ofs << 1) + 1;
}
}
- /* now that arr[tosort[size-ofs-1]*len] < key <= arr[tosort[size-last_ofs-1]*len] */
+ /* now that arr[tosort[size-ofs-1]*len] < key <=
+ * arr[tosort[size-last_ofs-1]*len] */
l = size - ofs - 1;
r = size - last_ofs - 1;
while (l + 1 < r) {
m = l + ((r - l) >> 1);
- if (@TYPE@_LT(arr + tosort[m] * len, key, len)) {
+ if (Tag::less(arr + tosort[m] * len, key, len)) {
l = m;
- } else {
+ }
+ else {
r = m;
}
}
@@ -1461,14 +1555,14 @@ agallop_left_@suff@(const @type@ *arr, const npy_intp *tosort,
return r;
}
-
+template <typename Tag, typename type>
static npy_intp
-agallop_right_@suff@(const @type@ *arr, const npy_intp *tosort,
- const npy_intp size, const @type@ *key, size_t len)
+agallop_right_(const type *arr, const npy_intp *tosort, const npy_intp size,
+ const type *key, size_t len)
{
npy_intp last_ofs, ofs, m;
- if (@TYPE@_LT(key, arr + tosort[0] * len, len)) {
+ if (Tag::less(key, arr + tosort[0] * len, len)) {
return 0;
}
@@ -1481,9 +1575,10 @@ agallop_right_@suff@(const @type@ *arr, const npy_intp *tosort,
break;
}
- if (@TYPE@_LT(key, arr + tosort[ofs] * len, len)) {
+ if (Tag::less(key, arr + tosort[ofs] * len, len)) {
break;
- } else {
+ }
+ else {
last_ofs = ofs;
/* ofs = 1, 3, 7, 15... */
ofs = (ofs << 1) + 1;
@@ -1494,9 +1589,10 @@ agallop_right_@suff@(const @type@ *arr, const npy_intp *tosort,
while (last_ofs + 1 < ofs) {
m = last_ofs + ((ofs - last_ofs) >> 1);
- if (@TYPE@_LT(key, arr + tosort[m] * len, len)) {
+ if (Tag::less(key, arr + tosort[m] * len, len)) {
ofs = m;
- } else {
+ }
+ else {
last_ofs = m;
}
}
@@ -1505,11 +1601,10 @@ agallop_right_@suff@(const @type@ *arr, const npy_intp *tosort,
return ofs;
}
-
-
+template <typename Tag, typename type>
static void
-amerge_left_@suff@(@type@ *arr, npy_intp *p1, npy_intp l1, npy_intp *p2,
- npy_intp l2, npy_intp *p3, size_t len)
+amerge_left_(type *arr, npy_intp *p1, npy_intp l1, npy_intp *p2, npy_intp l2,
+ npy_intp *p3, size_t len)
{
npy_intp *end = p2 + l2;
memcpy(p3, p1, sizeof(npy_intp) * l1);
@@ -1517,9 +1612,10 @@ amerge_left_@suff@(@type@ *arr, npy_intp *p1, npy_intp l1, npy_intp *p2,
*p1++ = *p2++;
while (p1 < p2 && p2 < end) {
- if (@TYPE@_LT(arr + (*p2) * len, arr + (*p3) * len, len)) {
+ if (Tag::less(arr + (*p2) * len, arr + (*p3) * len, len)) {
*p1++ = *p2++;
- } else {
+ }
+ else {
*p1++ = *p3++;
}
}
@@ -1529,10 +1625,10 @@ amerge_left_@suff@(@type@ *arr, npy_intp *p1, npy_intp l1, npy_intp *p2,
}
}
-
+template <typename Tag, typename type>
static void
-amerge_right_@suff@(@type@ *arr, npy_intp* p1, npy_intp l1, npy_intp *p2,
- npy_intp l2, npy_intp *p3, size_t len)
+amerge_right_(type *arr, npy_intp *p1, npy_intp l1, npy_intp *p2, npy_intp l2,
+ npy_intp *p3, size_t len)
{
npy_intp ofs;
npy_intp *start = p1 - 1;
@@ -1544,9 +1640,10 @@ amerge_right_@suff@(@type@ *arr, npy_intp* p1, npy_intp l1, npy_intp *p2,
*p2-- = *p1--;
while (p1 < p2 && start < p1) {
- if (@TYPE@_LT(arr + (*p3) * len, arr + (*p1) * len, len)) {
+ if (Tag::less(arr + (*p3) * len, arr + (*p1) * len, len)) {
*p2-- = *p1--;
- } else {
+ }
+ else {
*p2-- = *p3--;
}
}
@@ -1557,11 +1654,10 @@ amerge_right_@suff@(@type@ *arr, npy_intp* p1, npy_intp l1, npy_intp *p2,
}
}
-
-
+template <typename Tag, typename type>
static int
-amerge_at_@suff@(@type@ *arr, npy_intp *tosort, const run *stack,
- const npy_intp at, buffer_intp *buffer, size_t len)
+amerge_at_(type *arr, npy_intp *tosort, const run *stack, const npy_intp at,
+ buffer_intp *buffer, size_t len)
{
int ret;
npy_intp s1, l1, s2, l2, k;
@@ -1571,7 +1667,7 @@ amerge_at_@suff@(@type@ *arr, npy_intp *tosort, const run *stack,
s2 = stack[at + 1].s;
l2 = stack[at + 1].l;
/* tosort[s2] belongs to tosort[s1+k] */
- k = agallop_right_@suff@(arr, tosort + s1, l1, arr + tosort[s2] * len, len);
+ k = agallop_right_<Tag>(arr, tosort + s1, l1, arr + tosort[s2] * len, len);
if (l1 == k) {
/* already sorted */
@@ -1582,30 +1678,35 @@ amerge_at_@suff@(@type@ *arr, npy_intp *tosort, const run *stack,
l1 -= k;
p2 = tosort + s2;
/* tosort[s2-1] belongs to tosort[s2+l2] */
- l2 = agallop_left_@suff@(arr, tosort + s2, l2, arr + tosort[s2 - 1] * len,
- len);
+ l2 = agallop_left_<Tag>(arr, tosort + s2, l2, arr + tosort[s2 - 1] * len,
+ len);
if (l2 < l1) {
ret = resize_buffer_intp(buffer, l2);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
- amerge_right_@suff@(arr, p1, l1, p2, l2, buffer->pw, len);
- } else {
+ amerge_right_<Tag>(arr, p1, l1, p2, l2, buffer->pw, len);
+ }
+ else {
ret = resize_buffer_intp(buffer, l1);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
- amerge_left_@suff@(arr, p1, l1, p2, l2, buffer->pw, len);
+ amerge_left_<Tag>(arr, p1, l1, p2, l2, buffer->pw, len);
}
return 0;
}
-
+template <typename Tag, typename type>
static int
-atry_collapse_@suff@(@type@ *arr, npy_intp *tosort, run *stack,
- npy_intp *stack_ptr, buffer_intp *buffer, size_t len)
+atry_collapse_(type *arr, npy_intp *tosort, run *stack, npy_intp *stack_ptr,
+ buffer_intp *buffer, size_t len)
{
int ret;
npy_intp A, B, C, top;
@@ -1616,33 +1717,44 @@ atry_collapse_@suff@(@type@ *arr, npy_intp *tosort, run *stack,
C = stack[top - 1].l;
if ((2 < top && stack[top - 3].l <= B + C) ||
- (3 < top && stack[top - 4].l <= stack[top - 3].l + B)) {
+ (3 < top && stack[top - 4].l <= stack[top - 3].l + B)) {
A = stack[top - 3].l;
if (A <= C) {
- ret = amerge_at_@suff@(arr, tosort, stack, top - 3, buffer, len);
+ ret = amerge_at_<Tag>(arr, tosort, stack, top - 3, buffer,
+ len);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 3].l += B;
stack[top - 2] = stack[top - 1];
--top;
- } else {
- ret = amerge_at_@suff@(arr, tosort, stack, top - 2, buffer, len);
+ }
+ else {
+ ret = amerge_at_<Tag>(arr, tosort, stack, top - 2, buffer,
+ len);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 2].l += C;
--top;
}
- } else if (1 < top && B <= C) {
- ret = amerge_at_@suff@(arr, tosort, stack, top - 2, buffer, len);
+ }
+ else if (1 < top && B <= C) {
+ ret = amerge_at_<Tag>(arr, tosort, stack, top - 2, buffer, len);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 2].l += C;
--top;
- } else {
+ }
+ else {
break;
}
}
@@ -1651,28 +1763,32 @@ atry_collapse_@suff@(@type@ *arr, npy_intp *tosort, run *stack,
return 0;
}
-
-
+template <typename Tag, typename type>
static int
-aforce_collapse_@suff@(@type@ *arr, npy_intp *tosort, run *stack,
- npy_intp *stack_ptr, buffer_intp *buffer, size_t len)
+aforce_collapse_(type *arr, npy_intp *tosort, run *stack, npy_intp *stack_ptr,
+ buffer_intp *buffer, size_t len)
{
int ret;
npy_intp top = *stack_ptr;
while (2 < top) {
if (stack[top - 3].l <= stack[top - 1].l) {
- ret = amerge_at_@suff@(arr, tosort, stack, top - 3, buffer, len);
+ ret = amerge_at_<Tag>(arr, tosort, stack, top - 3, buffer, len);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 3].l += stack[top - 2].l;
stack[top - 2] = stack[top - 1];
--top;
- } else {
- ret = amerge_at_@suff@(arr, tosort, stack, top - 2, buffer, len);
+ }
+ else {
+ ret = amerge_at_<Tag>(arr, tosort, stack, top - 2, buffer, len);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 2].l += stack[top - 1].l;
--top;
@@ -1680,21 +1796,24 @@ aforce_collapse_@suff@(@type@ *arr, npy_intp *tosort, run *stack,
}
if (1 < top) {
- ret = amerge_at_@suff@(arr, tosort, stack, top - 2, buffer, len);
+ ret = amerge_at_<Tag>(arr, tosort, stack, top - 2, buffer, len);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
}
return 0;
}
-
+template <typename Tag>
NPY_NO_EXPORT int
-atimsort_@suff@(void *start, npy_intp *tosort, npy_intp num, void *varr)
+string_atimsort_(void *start, npy_intp *tosort, npy_intp num, void *varr)
{
- PyArrayObject *arr = varr;
+ using type = typename Tag::type;
+ PyArrayObject *arr = reinterpret_cast<PyArrayObject *>(varr);
size_t elsize = PyArray_ITEMSIZE(arr);
- size_t len = elsize / sizeof(@type@);
+ size_t len = elsize / sizeof(type);
int ret;
npy_intp l, n, stack_ptr, minrun;
run stack[TIMSORT_STACK_SIZE];
@@ -1711,21 +1830,27 @@ atimsort_@suff@(void *start, npy_intp *tosort, npy_intp num, void *varr)
minrun = compute_min_run_short(num);
for (l = 0; l < num;) {
- n = acount_run_@suff@(start, tosort, l, num, minrun, len);
+ n = acount_run_<Tag>((type *)start, tosort, l, num, minrun, len);
/* both s and l are scaled by len */
stack[stack_ptr].s = l;
stack[stack_ptr].l = n;
++stack_ptr;
- ret = atry_collapse_@suff@(start, tosort, stack, &stack_ptr, &buffer, len);
+ ret = atry_collapse_<Tag>((type *)start, tosort, stack, &stack_ptr,
+ &buffer, len);
- if (NPY_UNLIKELY(ret < 0)) { goto cleanup; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ goto cleanup;
+ }
l += n;
}
- ret = aforce_collapse_@suff@(start, tosort, stack, &stack_ptr, &buffer, len);
+ ret = aforce_collapse_<Tag>((type *)start, tosort, stack, &stack_ptr,
+ &buffer, len);
- if (NPY_UNLIKELY(ret < 0)) { goto cleanup; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ goto cleanup;
+ }
ret = 0;
@@ -1736,25 +1861,18 @@ cleanup:
return ret;
}
-
-/**end repeat**/
-
-
-
/*
*****************************************************************************
** GENERIC SORT **
*****************************************************************************
*/
-
typedef struct {
char *pw;
npy_intp size;
size_t len;
} buffer_char;
-
static NPY_INLINE int
resize_buffer_char(buffer_char *buffer, npy_intp new_size)
{
@@ -1763,24 +1881,26 @@ resize_buffer_char(buffer_char *buffer, npy_intp new_size)
}
if (NPY_UNLIKELY(buffer->pw == NULL)) {
- buffer->pw = malloc(sizeof(char) * new_size * buffer->len);
- } else {
- buffer->pw = realloc(buffer->pw, sizeof(char) * new_size * buffer->len);
+ buffer->pw = (char *)malloc(sizeof(char) * new_size * buffer->len);
+ }
+ else {
+ buffer->pw = (char *)realloc(buffer->pw,
+ sizeof(char) * new_size * buffer->len);
}
buffer->size = new_size;
if (NPY_UNLIKELY(buffer->pw == NULL)) {
return -NPY_ENOMEM;
- } else {
+ }
+ else {
return 0;
}
}
-
static npy_intp
-npy_count_run(char *arr, npy_intp l, npy_intp num, npy_intp minrun,
- char *vp, size_t len, PyArray_CompareFunc *cmp, PyArrayObject *py_arr)
+npy_count_run(char *arr, npy_intp l, npy_intp num, npy_intp minrun, char *vp,
+ size_t len, PyArray_CompareFunc *cmp, PyArrayObject *py_arr)
{
npy_intp sz;
char *pl, *pi, *pj, *pr;
@@ -1793,12 +1913,15 @@ npy_count_run(char *arr, npy_intp l, npy_intp num, npy_intp minrun,
/* (not strictly) ascending sequence */
if (cmp(pl, pl + len, py_arr) <= 0) {
- for (pi = pl + len; pi < arr + (num - 1) * len
- && cmp(pi, pi + len, py_arr) <= 0; pi += len) {
+ for (pi = pl + len;
+ pi < arr + (num - 1) * len && cmp(pi, pi + len, py_arr) <= 0;
+ pi += len) {
}
- } else { /* (strictly) descending sequence */
- for (pi = pl + len; pi < arr + (num - 1) * len
- && cmp(pi + len, pi, py_arr) < 0; pi += len) {
+ }
+ else { /* (strictly) descending sequence */
+ for (pi = pl + len;
+ pi < arr + (num - 1) * len && cmp(pi + len, pi, py_arr) < 0;
+ pi += len) {
}
for (pj = pl, pr = pi; pj < pr; pj += len, pr -= len) {
@@ -1812,7 +1935,8 @@ npy_count_run(char *arr, npy_intp l, npy_intp num, npy_intp minrun,
if (sz < minrun) {
if (l + minrun < num) {
sz = minrun;
- } else {
+ }
+ else {
sz = num - l;
}
@@ -1835,7 +1959,6 @@ npy_count_run(char *arr, npy_intp l, npy_intp num, npy_intp minrun,
return sz;
}
-
static npy_intp
npy_gallop_right(const char *arr, const npy_intp size, const char *key,
size_t len, PyArray_CompareFunc *cmp, PyArrayObject *py_arr)
@@ -1857,7 +1980,8 @@ npy_gallop_right(const char *arr, const npy_intp size, const char *key,
if (cmp(key, arr + ofs * len, py_arr) < 0) {
break;
- } else {
+ }
+ else {
last_ofs = ofs;
/* ofs = 1, 3, 7, 15... */
ofs = (ofs << 1) + 1;
@@ -1870,7 +1994,8 @@ npy_gallop_right(const char *arr, const npy_intp size, const char *key,
if (cmp(key, arr + m * len, py_arr) < 0) {
ofs = m;
- } else {
+ }
+ else {
last_ofs = m;
}
}
@@ -1879,8 +2004,6 @@ npy_gallop_right(const char *arr, const npy_intp size, const char *key,
return ofs;
}
-
-
static npy_intp
npy_gallop_left(const char *arr, const npy_intp size, const char *key,
size_t len, PyArray_CompareFunc *cmp, PyArrayObject *py_arr)
@@ -1902,7 +2025,8 @@ npy_gallop_left(const char *arr, const npy_intp size, const char *key,
if (cmp(arr + (size - ofs - 1) * len, key, py_arr) < 0) {
break;
- } else {
+ }
+ else {
last_ofs = ofs;
ofs = (ofs << 1) + 1;
}
@@ -1917,7 +2041,8 @@ npy_gallop_left(const char *arr, const npy_intp size, const char *key,
if (cmp(arr + m * len, key, py_arr) < 0) {
l = m;
- } else {
+ }
+ else {
r = m;
}
}
@@ -1926,11 +2051,9 @@ npy_gallop_left(const char *arr, const npy_intp size, const char *key,
return r;
}
-
static void
-npy_merge_left(char *p1, npy_intp l1, char *p2, npy_intp l2,
- char *p3, size_t len,
- PyArray_CompareFunc *cmp, PyArrayObject *py_arr)
+npy_merge_left(char *p1, npy_intp l1, char *p2, npy_intp l2, char *p3,
+ size_t len, PyArray_CompareFunc *cmp, PyArrayObject *py_arr)
{
char *end = p2 + l2 * len;
memcpy(p3, p1, sizeof(char) * l1 * len);
@@ -1944,7 +2067,8 @@ npy_merge_left(char *p1, npy_intp l1, char *p2, npy_intp l2,
GENERIC_COPY(p1, p2, len);
p1 += len;
p2 += len;
- } else {
+ }
+ else {
GENERIC_COPY(p1, p3, len);
p1 += len;
p3 += len;
@@ -1956,11 +2080,9 @@ npy_merge_left(char *p1, npy_intp l1, char *p2, npy_intp l2,
}
}
-
static void
-npy_merge_right(char *p1, npy_intp l1, char *p2, npy_intp l2,
- char *p3, size_t len,
- PyArray_CompareFunc *cmp, PyArrayObject *py_arr)
+npy_merge_right(char *p1, npy_intp l1, char *p2, npy_intp l2, char *p3,
+ size_t len, PyArray_CompareFunc *cmp, PyArrayObject *py_arr)
{
npy_intp ofs;
char *start = p1 - len;
@@ -1978,7 +2100,8 @@ npy_merge_right(char *p1, npy_intp l1, char *p2, npy_intp l2,
GENERIC_COPY(p2, p1, len);
p2 -= len;
p1 -= len;
- } else {
+ }
+ else {
GENERIC_COPY(p2, p3, len);
p2 -= len;
p3 -= len;
@@ -1991,12 +2114,10 @@ npy_merge_right(char *p1, npy_intp l1, char *p2, npy_intp l2,
}
}
-
-
static int
npy_merge_at(char *arr, const run *stack, const npy_intp at,
- buffer_char *buffer, size_t len,
- PyArray_CompareFunc *cmp, PyArrayObject *py_arr)
+ buffer_char *buffer, size_t len, PyArray_CompareFunc *cmp,
+ PyArrayObject *py_arr)
{
int ret;
npy_intp s1, l1, s2, l2, k;
@@ -2024,13 +2145,18 @@ npy_merge_at(char *arr, const run *stack, const npy_intp at,
if (l2 < l1) {
ret = resize_buffer_char(buffer, l2);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
npy_merge_right(p1, l1, p2, l2, buffer->pw, len, cmp, py_arr);
- } else {
+ }
+ else {
ret = resize_buffer_char(buffer, l1);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
npy_merge_left(p1, l1, p2, l2, buffer->pw, len, cmp, py_arr);
}
@@ -2038,11 +2164,10 @@ npy_merge_at(char *arr, const run *stack, const npy_intp at,
return 0;
}
-
static int
npy_try_collapse(char *arr, run *stack, npy_intp *stack_ptr,
- buffer_char *buffer, size_t len,
- PyArray_CompareFunc *cmp, PyArrayObject *py_arr)
+ buffer_char *buffer, size_t len, PyArray_CompareFunc *cmp,
+ PyArrayObject *py_arr)
{
int ret;
npy_intp A, B, C, top;
@@ -2053,33 +2178,44 @@ npy_try_collapse(char *arr, run *stack, npy_intp *stack_ptr,
C = stack[top - 1].l;
if ((2 < top && stack[top - 3].l <= B + C) ||
- (3 < top && stack[top - 4].l <= stack[top - 3].l + B)) {
+ (3 < top && stack[top - 4].l <= stack[top - 3].l + B)) {
A = stack[top - 3].l;
if (A <= C) {
- ret = npy_merge_at(arr, stack, top - 3, buffer, len, cmp, py_arr);
+ ret = npy_merge_at(arr, stack, top - 3, buffer, len, cmp,
+ py_arr);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 3].l += B;
stack[top - 2] = stack[top - 1];
--top;
- } else {
- ret = npy_merge_at(arr, stack, top - 2, buffer, len, cmp, py_arr);
+ }
+ else {
+ ret = npy_merge_at(arr, stack, top - 2, buffer, len, cmp,
+ py_arr);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 2].l += C;
--top;
}
- } else if (1 < top && B <= C) {
+ }
+ else if (1 < top && B <= C) {
ret = npy_merge_at(arr, stack, top - 2, buffer, len, cmp, py_arr);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 2].l += C;
--top;
- } else {
+ }
+ else {
break;
}
}
@@ -2088,11 +2224,10 @@ npy_try_collapse(char *arr, run *stack, npy_intp *stack_ptr,
return 0;
}
-
static int
npy_force_collapse(char *arr, run *stack, npy_intp *stack_ptr,
- buffer_char *buffer, size_t len,
- PyArray_CompareFunc *cmp, PyArrayObject *py_arr)
+ buffer_char *buffer, size_t len, PyArray_CompareFunc *cmp,
+ PyArrayObject *py_arr)
{
int ret;
npy_intp top = *stack_ptr;
@@ -2101,15 +2236,20 @@ npy_force_collapse(char *arr, run *stack, npy_intp *stack_ptr,
if (stack[top - 3].l <= stack[top - 1].l) {
ret = npy_merge_at(arr, stack, top - 3, buffer, len, cmp, py_arr);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 3].l += stack[top - 2].l;
stack[top - 2] = stack[top - 1];
--top;
- } else {
+ }
+ else {
ret = npy_merge_at(arr, stack, top - 2, buffer, len, cmp, py_arr);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 2].l += stack[top - 1].l;
--top;
@@ -2119,17 +2259,18 @@ npy_force_collapse(char *arr, run *stack, npy_intp *stack_ptr,
if (1 < top) {
ret = npy_merge_at(arr, stack, top - 2, buffer, len, cmp, py_arr);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
}
return 0;
}
-
NPY_NO_EXPORT int
npy_timsort(void *start, npy_intp num, void *varr)
{
- PyArrayObject *arr = varr;
+ PyArrayObject *arr = reinterpret_cast<PyArrayObject *>(varr);
size_t len = PyArray_ITEMSIZE(arr);
PyArray_CompareFunc *cmp = PyArray_DESCR(arr)->f->compare;
int ret;
@@ -2151,25 +2292,34 @@ npy_timsort(void *start, npy_intp num, void *varr)
/* used for insertion sort and gallop key */
ret = resize_buffer_char(&buffer, len);
- if (NPY_UNLIKELY(ret < 0)) { goto cleanup; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ goto cleanup;
+ }
for (l = 0; l < num;) {
- n = npy_count_run(start, l, num, minrun, buffer.pw, len, cmp, arr);
+ n = npy_count_run((char *)start, l, num, minrun, buffer.pw, len, cmp,
+ arr);
/* both s and l are scaled by len */
stack[stack_ptr].s = l;
stack[stack_ptr].l = n;
++stack_ptr;
- ret = npy_try_collapse(start, stack, &stack_ptr, &buffer, len, cmp, arr);
+ ret = npy_try_collapse((char *)start, stack, &stack_ptr, &buffer, len,
+ cmp, arr);
- if (NPY_UNLIKELY(ret < 0)) { goto cleanup; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ goto cleanup;
+ }
l += n;
}
- ret = npy_force_collapse(start, stack, &stack_ptr, &buffer, len, cmp, arr);
+ ret = npy_force_collapse((char *)start, stack, &stack_ptr, &buffer, len,
+ cmp, arr);
- if (NPY_UNLIKELY(ret < 0)) { goto cleanup; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ goto cleanup;
+ }
ret = 0;
@@ -2180,13 +2330,12 @@ cleanup:
return ret;
}
-
/* argsort */
static npy_intp
npy_acount_run(char *arr, npy_intp *tosort, npy_intp l, npy_intp num,
- npy_intp minrun, size_t len,
- PyArray_CompareFunc *cmp, PyArrayObject *py_arr)
+ npy_intp minrun, size_t len, PyArray_CompareFunc *cmp,
+ PyArrayObject *py_arr)
{
npy_intp sz;
npy_intp vi;
@@ -2200,16 +2349,21 @@ npy_acount_run(char *arr, npy_intp *tosort, npy_intp l, npy_intp num,
/* (not strictly) ascending sequence */
if (cmp(arr + (*pl) * len, arr + (*(pl + 1)) * len, py_arr) <= 0) {
- for (pi = pl + 1; pi < tosort + num - 1
- && cmp(arr + (*pi) * len, arr + (*(pi + 1)) * len, py_arr) <= 0; ++pi) {
+ for (pi = pl + 1;
+ pi < tosort + num - 1 &&
+ cmp(arr + (*pi) * len, arr + (*(pi + 1)) * len, py_arr) <= 0;
+ ++pi) {
}
- } else { /* (strictly) descending sequence */
- for (pi = pl + 1; pi < tosort + num - 1
- && cmp(arr + (*(pi + 1)) * len, arr + (*pi) * len, py_arr) < 0; ++pi) {
+ }
+ else { /* (strictly) descending sequence */
+ for (pi = pl + 1;
+ pi < tosort + num - 1 &&
+ cmp(arr + (*(pi + 1)) * len, arr + (*pi) * len, py_arr) < 0;
+ ++pi) {
}
for (pj = pl, pr = pi; pj < pr; ++pj, --pr) {
- INTP_SWAP(*pj, *pr);
+ std::swap(*pj, *pr);
}
}
@@ -2219,7 +2373,8 @@ npy_acount_run(char *arr, npy_intp *tosort, npy_intp l, npy_intp num,
if (sz < minrun) {
if (l + minrun < num) {
sz = minrun;
- } else {
+ }
+ else {
sz = num - l;
}
@@ -2230,7 +2385,8 @@ npy_acount_run(char *arr, npy_intp *tosort, npy_intp l, npy_intp num,
vi = *pi;
pj = pi;
- while (pl < pj && cmp(arr + vi * len, arr + (*(pj - 1)) * len, py_arr) < 0) {
+ while (pl < pj &&
+ cmp(arr + vi * len, arr + (*(pj - 1)) * len, py_arr) < 0) {
*pj = *(pj - 1);
--pj;
}
@@ -2242,11 +2398,10 @@ npy_acount_run(char *arr, npy_intp *tosort, npy_intp l, npy_intp num,
return sz;
}
-
static npy_intp
-npy_agallop_left(const char *arr, const npy_intp *tosort,
- const npy_intp size, const char *key, size_t len,
- PyArray_CompareFunc *cmp, PyArrayObject *py_arr)
+npy_agallop_left(const char *arr, const npy_intp *tosort, const npy_intp size,
+ const char *key, size_t len, PyArray_CompareFunc *cmp,
+ PyArrayObject *py_arr)
{
npy_intp last_ofs, ofs, l, m, r;
@@ -2265,13 +2420,15 @@ npy_agallop_left(const char *arr, const npy_intp *tosort,
if (cmp(arr + tosort[size - ofs - 1] * len, key, py_arr) < 0) {
break;
- } else {
+ }
+ else {
last_ofs = ofs;
ofs = (ofs << 1) + 1;
}
}
- /* now that arr[tosort[size-ofs-1]*len] < key <= arr[tosort[size-last_ofs-1]*len] */
+ /* now that arr[tosort[size-ofs-1]*len] < key <=
+ * arr[tosort[size-last_ofs-1]*len] */
l = size - ofs - 1;
r = size - last_ofs - 1;
@@ -2280,7 +2437,8 @@ npy_agallop_left(const char *arr, const npy_intp *tosort,
if (cmp(arr + tosort[m] * len, key, py_arr) < 0) {
l = m;
- } else {
+ }
+ else {
r = m;
}
}
@@ -2289,11 +2447,10 @@ npy_agallop_left(const char *arr, const npy_intp *tosort,
return r;
}
-
static npy_intp
-npy_agallop_right(const char *arr, const npy_intp *tosort,
- const npy_intp size, const char *key, size_t len,
- PyArray_CompareFunc *cmp, PyArrayObject *py_arr)
+npy_agallop_right(const char *arr, const npy_intp *tosort, const npy_intp size,
+ const char *key, size_t len, PyArray_CompareFunc *cmp,
+ PyArrayObject *py_arr)
{
npy_intp last_ofs, ofs, m;
@@ -2312,7 +2469,8 @@ npy_agallop_right(const char *arr, const npy_intp *tosort,
if (cmp(key, arr + tosort[ofs] * len, py_arr) < 0) {
break;
- } else {
+ }
+ else {
last_ofs = ofs;
/* ofs = 1, 3, 7, 15... */
ofs = (ofs << 1) + 1;
@@ -2325,7 +2483,8 @@ npy_agallop_right(const char *arr, const npy_intp *tosort,
if (cmp(key, arr + tosort[m] * len, py_arr) < 0) {
ofs = m;
- } else {
+ }
+ else {
last_ofs = m;
}
}
@@ -2334,7 +2493,6 @@ npy_agallop_right(const char *arr, const npy_intp *tosort,
return ofs;
}
-
static void
npy_amerge_left(char *arr, npy_intp *p1, npy_intp l1, npy_intp *p2,
npy_intp l2, npy_intp *p3, size_t len,
@@ -2348,7 +2506,8 @@ npy_amerge_left(char *arr, npy_intp *p1, npy_intp l1, npy_intp *p2,
while (p1 < p2 && p2 < end) {
if (cmp(arr + (*p2) * len, arr + (*p3) * len, py_arr) < 0) {
*p1++ = *p2++;
- } else {
+ }
+ else {
*p1++ = *p3++;
}
}
@@ -2358,9 +2517,8 @@ npy_amerge_left(char *arr, npy_intp *p1, npy_intp l1, npy_intp *p2,
}
}
-
static void
-npy_amerge_right(char *arr, npy_intp* p1, npy_intp l1, npy_intp *p2,
+npy_amerge_right(char *arr, npy_intp *p1, npy_intp l1, npy_intp *p2,
npy_intp l2, npy_intp *p3, size_t len,
PyArray_CompareFunc *cmp, PyArrayObject *py_arr)
{
@@ -2376,7 +2534,8 @@ npy_amerge_right(char *arr, npy_intp* p1, npy_intp l1, npy_intp *p2,
while (p1 < p2 && start < p1) {
if (cmp(arr + (*p3) * len, arr + (*p1) * len, py_arr) < 0) {
*p2-- = *p1--;
- } else {
+ }
+ else {
*p2-- = *p3--;
}
}
@@ -2387,12 +2546,10 @@ npy_amerge_right(char *arr, npy_intp* p1, npy_intp l1, npy_intp *p2,
}
}
-
-
static int
-npy_amerge_at(char *arr, npy_intp *tosort, const run *stack,
- const npy_intp at, buffer_intp *buffer, size_t len,
- PyArray_CompareFunc *cmp, PyArrayObject *py_arr)
+npy_amerge_at(char *arr, npy_intp *tosort, const run *stack, const npy_intp at,
+ buffer_intp *buffer, size_t len, PyArray_CompareFunc *cmp,
+ PyArrayObject *py_arr)
{
int ret;
npy_intp s1, l1, s2, l2, k;
@@ -2402,8 +2559,8 @@ npy_amerge_at(char *arr, npy_intp *tosort, const run *stack,
s2 = stack[at + 1].s;
l2 = stack[at + 1].l;
/* tosort[s2] belongs to tosort[s1+k] */
- k = npy_agallop_right(arr, tosort + s1, l1, arr + tosort[s2] * len, len, cmp,
- py_arr);
+ k = npy_agallop_right(arr, tosort + s1, l1, arr + tosort[s2] * len, len,
+ cmp, py_arr);
if (l1 == k) {
/* already sorted */
@@ -2420,13 +2577,18 @@ npy_amerge_at(char *arr, npy_intp *tosort, const run *stack,
if (l2 < l1) {
ret = resize_buffer_intp(buffer, l2);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
npy_amerge_right(arr, p1, l1, p2, l2, buffer->pw, len, cmp, py_arr);
- } else {
+ }
+ else {
ret = resize_buffer_intp(buffer, l1);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
npy_amerge_left(arr, p1, l1, p2, l2, buffer->pw, len, cmp, py_arr);
}
@@ -2434,11 +2596,10 @@ npy_amerge_at(char *arr, npy_intp *tosort, const run *stack,
return 0;
}
-
static int
-npy_atry_collapse(char *arr, npy_intp *tosort, run *stack,
- npy_intp *stack_ptr, buffer_intp *buffer, size_t len,
- PyArray_CompareFunc *cmp, PyArrayObject *py_arr)
+npy_atry_collapse(char *arr, npy_intp *tosort, run *stack, npy_intp *stack_ptr,
+ buffer_intp *buffer, size_t len, PyArray_CompareFunc *cmp,
+ PyArrayObject *py_arr)
{
int ret;
npy_intp A, B, C, top;
@@ -2449,33 +2610,45 @@ npy_atry_collapse(char *arr, npy_intp *tosort, run *stack,
C = stack[top - 1].l;
if ((2 < top && stack[top - 3].l <= B + C) ||
- (3 < top && stack[top - 4].l <= stack[top - 3].l + B)) {
+ (3 < top && stack[top - 4].l <= stack[top - 3].l + B)) {
A = stack[top - 3].l;
if (A <= C) {
- ret = npy_amerge_at(arr, tosort, stack, top - 3, buffer, len, cmp, py_arr);
+ ret = npy_amerge_at(arr, tosort, stack, top - 3, buffer, len,
+ cmp, py_arr);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 3].l += B;
stack[top - 2] = stack[top - 1];
--top;
- } else {
- ret = npy_amerge_at(arr, tosort, stack, top - 2, buffer, len, cmp, py_arr);
+ }
+ else {
+ ret = npy_amerge_at(arr, tosort, stack, top - 2, buffer, len,
+ cmp, py_arr);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 2].l += C;
--top;
}
- } else if (1 < top && B <= C) {
- ret = npy_amerge_at(arr, tosort, stack, top - 2, buffer, len, cmp, py_arr);
+ }
+ else if (1 < top && B <= C) {
+ ret = npy_amerge_at(arr, tosort, stack, top - 2, buffer, len, cmp,
+ py_arr);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 2].l += C;
--top;
- } else {
+ }
+ else {
break;
}
}
@@ -2484,7 +2657,6 @@ npy_atry_collapse(char *arr, npy_intp *tosort, run *stack,
return 0;
}
-
static int
npy_aforce_collapse(char *arr, npy_intp *tosort, run *stack,
npy_intp *stack_ptr, buffer_intp *buffer, size_t len,
@@ -2495,17 +2667,24 @@ npy_aforce_collapse(char *arr, npy_intp *tosort, run *stack,
while (2 < top) {
if (stack[top - 3].l <= stack[top - 1].l) {
- ret = npy_amerge_at(arr, tosort, stack, top - 3, buffer, len, cmp, py_arr);
+ ret = npy_amerge_at(arr, tosort, stack, top - 3, buffer, len, cmp,
+ py_arr);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 3].l += stack[top - 2].l;
stack[top - 2] = stack[top - 1];
--top;
- } else {
- ret = npy_amerge_at(arr, tosort, stack, top - 2, buffer, len, cmp, py_arr);
+ }
+ else {
+ ret = npy_amerge_at(arr, tosort, stack, top - 2, buffer, len, cmp,
+ py_arr);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
stack[top - 2].l += stack[top - 1].l;
--top;
@@ -2513,19 +2692,21 @@ npy_aforce_collapse(char *arr, npy_intp *tosort, run *stack,
}
if (1 < top) {
- ret = npy_amerge_at(arr, tosort, stack, top - 2, buffer, len, cmp, py_arr);
+ ret = npy_amerge_at(arr, tosort, stack, top - 2, buffer, len, cmp,
+ py_arr);
- if (NPY_UNLIKELY(ret < 0)) { return ret; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ return ret;
+ }
}
return 0;
}
-
NPY_NO_EXPORT int
npy_atimsort(void *start, npy_intp *tosort, npy_intp num, void *varr)
{
- PyArrayObject *arr = varr;
+ PyArrayObject *arr = reinterpret_cast<PyArrayObject *>(varr);
size_t len = PyArray_ITEMSIZE(arr);
PyArray_CompareFunc *cmp = PyArray_DESCR(arr)->f->compare;
int ret;
@@ -2544,23 +2725,28 @@ npy_atimsort(void *start, npy_intp *tosort, npy_intp num, void *varr)
minrun = compute_min_run_short(num);
for (l = 0; l < num;) {
- n = npy_acount_run(start, tosort, l, num, minrun, len, cmp, arr);
+ n = npy_acount_run((char *)start, tosort, l, num, minrun, len, cmp,
+ arr);
/* both s and l are scaled by len */
stack[stack_ptr].s = l;
stack[stack_ptr].l = n;
++stack_ptr;
- ret = npy_atry_collapse(start, tosort, stack, &stack_ptr, &buffer, len, cmp,
- arr);
+ ret = npy_atry_collapse((char *)start, tosort, stack, &stack_ptr,
+ &buffer, len, cmp, arr);
- if (NPY_UNLIKELY(ret < 0)) { goto cleanup; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ goto cleanup;
+ }
l += n;
}
- ret = npy_aforce_collapse(start, tosort, stack, &stack_ptr, &buffer, len,
- cmp, arr);
+ ret = npy_aforce_collapse((char *)start, tosort, stack, &stack_ptr,
+ &buffer, len, cmp, arr);
- if (NPY_UNLIKELY(ret < 0)) { goto cleanup; }
+ if (NPY_UNLIKELY(ret < 0)) {
+ goto cleanup;
+ }
ret = 0;
@@ -2570,3 +2756,239 @@ cleanup:
}
return ret;
}
+
+/***************************************
+ * C > C++ dispatch
+ ***************************************/
+
+NPY_NO_EXPORT int
+timsort_bool(void *start, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return timsort_<npy::bool_tag>(start, num);
+}
+NPY_NO_EXPORT int
+timsort_byte(void *start, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return timsort_<npy::byte_tag>(start, num);
+}
+NPY_NO_EXPORT int
+timsort_ubyte(void *start, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return timsort_<npy::ubyte_tag>(start, num);
+}
+NPY_NO_EXPORT int
+timsort_short(void *start, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return timsort_<npy::short_tag>(start, num);
+}
+NPY_NO_EXPORT int
+timsort_ushort(void *start, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return timsort_<npy::ushort_tag>(start, num);
+}
+NPY_NO_EXPORT int
+timsort_int(void *start, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return timsort_<npy::int_tag>(start, num);
+}
+NPY_NO_EXPORT int
+timsort_uint(void *start, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return timsort_<npy::uint_tag>(start, num);
+}
+NPY_NO_EXPORT int
+timsort_long(void *start, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return timsort_<npy::long_tag>(start, num);
+}
+NPY_NO_EXPORT int
+timsort_ulong(void *start, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return timsort_<npy::ulong_tag>(start, num);
+}
+NPY_NO_EXPORT int
+timsort_longlong(void *start, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return timsort_<npy::longlong_tag>(start, num);
+}
+NPY_NO_EXPORT int
+timsort_ulonglong(void *start, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return timsort_<npy::ulonglong_tag>(start, num);
+}
+NPY_NO_EXPORT int
+timsort_half(void *start, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return timsort_<npy::half_tag>(start, num);
+}
+NPY_NO_EXPORT int
+timsort_float(void *start, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return timsort_<npy::float_tag>(start, num);
+}
+NPY_NO_EXPORT int
+timsort_double(void *start, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return timsort_<npy::double_tag>(start, num);
+}
+NPY_NO_EXPORT int
+timsort_longdouble(void *start, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return timsort_<npy::longdouble_tag>(start, num);
+}
+NPY_NO_EXPORT int
+timsort_cfloat(void *start, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return timsort_<npy::cfloat_tag>(start, num);
+}
+NPY_NO_EXPORT int
+timsort_cdouble(void *start, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return timsort_<npy::cdouble_tag>(start, num);
+}
+NPY_NO_EXPORT int
+timsort_clongdouble(void *start, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return timsort_<npy::clongdouble_tag>(start, num);
+}
+NPY_NO_EXPORT int
+timsort_datetime(void *start, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return timsort_<npy::datetime_tag>(start, num);
+}
+NPY_NO_EXPORT int
+timsort_timedelta(void *start, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return timsort_<npy::timedelta_tag>(start, num);
+}
+NPY_NO_EXPORT int
+timsort_string(void *start, npy_intp num, void *varr)
+{
+ return string_timsort_<npy::string_tag>(start, num, varr);
+}
+NPY_NO_EXPORT int
+timsort_unicode(void *start, npy_intp num, void *varr)
+{
+ return string_timsort_<npy::unicode_tag>(start, num, varr);
+}
+
+NPY_NO_EXPORT int
+atimsort_bool(void *v, npy_intp *tosort, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return atimsort_<npy::bool_tag>(v, tosort, num);
+}
+NPY_NO_EXPORT int
+atimsort_byte(void *v, npy_intp *tosort, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return atimsort_<npy::byte_tag>(v, tosort, num);
+}
+NPY_NO_EXPORT int
+atimsort_ubyte(void *v, npy_intp *tosort, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return atimsort_<npy::ubyte_tag>(v, tosort, num);
+}
+NPY_NO_EXPORT int
+atimsort_short(void *v, npy_intp *tosort, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return atimsort_<npy::short_tag>(v, tosort, num);
+}
+NPY_NO_EXPORT int
+atimsort_ushort(void *v, npy_intp *tosort, npy_intp num,
+ void *NPY_UNUSED(varr))
+{
+ return atimsort_<npy::ushort_tag>(v, tosort, num);
+}
+NPY_NO_EXPORT int
+atimsort_int(void *v, npy_intp *tosort, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return atimsort_<npy::int_tag>(v, tosort, num);
+}
+NPY_NO_EXPORT int
+atimsort_uint(void *v, npy_intp *tosort, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return atimsort_<npy::uint_tag>(v, tosort, num);
+}
+NPY_NO_EXPORT int
+atimsort_long(void *v, npy_intp *tosort, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return atimsort_<npy::long_tag>(v, tosort, num);
+}
+NPY_NO_EXPORT int
+atimsort_ulong(void *v, npy_intp *tosort, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return atimsort_<npy::ulong_tag>(v, tosort, num);
+}
+NPY_NO_EXPORT int
+atimsort_longlong(void *v, npy_intp *tosort, npy_intp num,
+ void *NPY_UNUSED(varr))
+{
+ return atimsort_<npy::longlong_tag>(v, tosort, num);
+}
+NPY_NO_EXPORT int
+atimsort_ulonglong(void *v, npy_intp *tosort, npy_intp num,
+ void *NPY_UNUSED(varr))
+{
+ return atimsort_<npy::ulonglong_tag>(v, tosort, num);
+}
+NPY_NO_EXPORT int
+atimsort_half(void *v, npy_intp *tosort, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return atimsort_<npy::half_tag>(v, tosort, num);
+}
+NPY_NO_EXPORT int
+atimsort_float(void *v, npy_intp *tosort, npy_intp num, void *NPY_UNUSED(varr))
+{
+ return atimsort_<npy::float_tag>(v, tosort, num);
+}
+NPY_NO_EXPORT int
+atimsort_double(void *v, npy_intp *tosort, npy_intp num,
+ void *NPY_UNUSED(varr))
+{
+ return atimsort_<npy::double_tag>(v, tosort, num);
+}
+NPY_NO_EXPORT int
+atimsort_longdouble(void *v, npy_intp *tosort, npy_intp num,
+ void *NPY_UNUSED(varr))
+{
+ return atimsort_<npy::longdouble_tag>(v, tosort, num);
+}
+NPY_NO_EXPORT int
+atimsort_cfloat(void *v, npy_intp *tosort, npy_intp num,
+ void *NPY_UNUSED(varr))
+{
+ return atimsort_<npy::cfloat_tag>(v, tosort, num);
+}
+NPY_NO_EXPORT int
+atimsort_cdouble(void *v, npy_intp *tosort, npy_intp num,
+ void *NPY_UNUSED(varr))
+{
+ return atimsort_<npy::cdouble_tag>(v, tosort, num);
+}
+NPY_NO_EXPORT int
+atimsort_clongdouble(void *v, npy_intp *tosort, npy_intp num,
+ void *NPY_UNUSED(varr))
+{
+ return atimsort_<npy::clongdouble_tag>(v, tosort, num);
+}
+NPY_NO_EXPORT int
+atimsort_datetime(void *v, npy_intp *tosort, npy_intp num,
+ void *NPY_UNUSED(varr))
+{
+ return atimsort_<npy::datetime_tag>(v, tosort, num);
+}
+NPY_NO_EXPORT int
+atimsort_timedelta(void *v, npy_intp *tosort, npy_intp num,
+ void *NPY_UNUSED(varr))
+{
+ return atimsort_<npy::timedelta_tag>(v, tosort, num);
+}
+NPY_NO_EXPORT int
+atimsort_string(void *v, npy_intp *tosort, npy_intp num, void *varr)
+{
+ return string_atimsort_<npy::string_tag>(v, tosort, num, varr);
+}
+NPY_NO_EXPORT int
+atimsort_unicode(void *v, npy_intp *tosort, npy_intp num, void *varr)
+{
+ return string_atimsort_<npy::unicode_tag>(v, tosort, num, varr);
+}
View Lorry Controller Status