summaryrefslogtreecommitdiffstatshomepage
path: root/3rdparty/bx/src/sort.cpp
diff options
context:
space:
mode:
Diffstat (limited to '3rdparty/bx/src/sort.cpp')
-rw-r--r--3rdparty/bx/src/sort.cpp55
1 files changed, 55 insertions, 0 deletions
diff --git a/3rdparty/bx/src/sort.cpp b/3rdparty/bx/src/sort.cpp
new file mode 100644
index 00000000000..3b7485fe7fe
--- /dev/null
+++ b/3rdparty/bx/src/sort.cpp
@@ -0,0 +1,55 @@
+/*
+ * Copyright 2010-2017 Branimir Karadzic. All rights reserved.
+ * License: https://github.com/bkaradzic/bx#license-bsd-2-clause
+ */
+
+#include <bx/sort.h>
+
+namespace bx
+{
+ static void quickSortR(void* _pivot, void* _data, uint32_t _num, uint32_t _stride, const ComparisonFn _fn)
+ {
+ if (2 > _num)
+ {
+ return;
+ }
+
+ memCopy(_pivot, _data, _stride);
+
+ uint8_t* data = (uint8_t*)_data;
+
+ uint32_t ll = 0;
+ uint32_t gg = 1;
+
+ for (uint32_t ii = 1; ii < _num;)
+ {
+ int32_t result = _fn(&data[ii*_stride], _pivot);
+ if (0 > result)
+ {
+ xchg(&data[ll*_stride], &data[ii*_stride], _stride);
+ ++ll;
+ }
+ else if (0 == result)
+ {
+ xchg(&data[gg*_stride], &data[ii*_stride], _stride);
+ ++gg;
+ ++ii;
+ }
+ else
+ {
+ ++ii;
+ }
+ }
+
+ quickSortR(_pivot, &data[0 ], ll, _stride, _fn);
+ quickSortR(_pivot, &data[gg*_stride], _num-gg, _stride, _fn);
+ }
+
+ void quickSort(void* _data, uint32_t _num, uint32_t _stride, const ComparisonFn _fn)
+ {
+ uint8_t* pivot = (uint8_t*)alloca(_stride);
+ quickSortR(pivot, _data, _num, _stride, _fn);
+ }
+
+} // namespace bx
+