summaryrefslogtreecommitdiffstatshomepage
path: root/3rdparty/bx/src/sort.cpp
diff options
context:
space:
mode:
author Miodrag Milanović <mmicko@gmail.com>2023-01-05 15:32:40 +0100
committer GitHub <noreply@github.com>2023-01-05 09:32:40 -0500
commit812e6094f47bb8d1da5a6b421aa4c724cf2035c0 (patch)
tree0f5bab2fe9393d1f629e9bf63e76cecca74ec0c9 /3rdparty/bx/src/sort.cpp
parent4a1b41854bba8fc2567906b88bab8ca81e75d187 (diff)
Update BGFX, BX and BIMG (#10789)
* Update to bgfx a93a714632b79b5ddbf5c86ac323fa9b76ed3433 Co-authored-by: Бранимир Караџић <branimirkaradzic@gmail.com>
Diffstat (limited to '3rdparty/bx/src/sort.cpp')
-rw-r--r--3rdparty/bx/src/sort.cpp124
1 files changed, 121 insertions, 3 deletions
diff --git a/3rdparty/bx/src/sort.cpp b/3rdparty/bx/src/sort.cpp
index ce1b3e3a8a4..31ad8c795f4 100644
--- a/3rdparty/bx/src/sort.cpp
+++ b/3rdparty/bx/src/sort.cpp
@@ -1,9 +1,8 @@
/*
- * Copyright 2010-2021 Branimir Karadzic. All rights reserved.
- * License: https://github.com/bkaradzic/bx#license-bsd-2-clause
+ * Copyright 2010-2022 Branimir Karadzic. All rights reserved.
+ * License: https://github.com/bkaradzic/bx/blob/master/LICENSE
*/
-#include "bx_p.h"
#include <bx/sort.h>
namespace bx
@@ -52,5 +51,124 @@ namespace bx
quickSortR(pivot, _data, _num, _stride, _fn);
}
+ bool isSorted(const void* _data, uint32_t _num, uint32_t _stride, const ComparisonFn _fn)
+ {
+ const uint8_t* data = (uint8_t*)_data;
+
+ for (uint32_t ii = 1; ii < _num; ++ii)
+ {
+ int32_t result = _fn(&data[(ii-1)*_stride], &data[ii*_stride]);
+
+ if (0 < result)
+ {
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+ uint32_t unique(void* _data, uint32_t _num, uint32_t _stride, const ComparisonFn _fn)
+ {
+ if (0 == _num)
+ {
+ return 0;
+ }
+
+ uint8_t* data = (uint8_t*)_data;
+
+ uint32_t last = 0;
+
+ for (uint32_t ii = 1; ii < _num; ++ii)
+ {
+ int32_t result = _fn(&data[last*_stride], &data[ii*_stride]);
+ BX_ASSERT(0 >= result, "Performing unique on non-sorted array (ii %d, last %d)!", ii, last);
+
+ if (0 > result)
+ {
+ last++;
+ swap(&data[last*_stride], &data[ii*_stride], _stride);
+ }
+ }
+
+ return last+1;
+ }
+
+ uint32_t lowerBound(const void* _key, const void* _data, uint32_t _num, uint32_t _stride, const ComparisonFn _fn)
+ {
+ uint32_t offset = 0;
+ const uint8_t* data = (uint8_t*)_data;
+
+ for (uint32_t ll = _num; offset < ll;)
+ {
+ const uint32_t idx = (offset + ll) / 2;
+
+ int32_t result = _fn(_key, &data[idx * _stride]);
+
+ if (result <= 0)
+ {
+ ll = idx;
+ }
+ else
+ {
+ offset = idx + 1;
+ }
+ }
+
+ return offset;
+ }
+
+ uint32_t upperBound(const void* _key, const void* _data, uint32_t _num, uint32_t _stride, const ComparisonFn _fn)
+ {
+ uint32_t offset = 0;
+ const uint8_t* data = (uint8_t*)_data;
+
+ for (uint32_t ll = _num; offset < ll;)
+ {
+ const uint32_t idx = (offset + ll) / 2;
+
+ int32_t result = _fn(_key, &data[idx * _stride]);
+
+ if (result < 0)
+ {
+ ll = idx;
+ }
+ else
+ {
+ offset = idx + 1;
+ }
+ }
+
+ return offset;
+ }
+
+ int32_t binarySearch(const void* _key, const void* _data, uint32_t _num, uint32_t _stride, const ComparisonFn _fn)
+ {
+ uint32_t offset = 0;
+ const uint8_t* data = (uint8_t*)_data;
+
+ for (uint32_t ll = _num; offset < ll;)
+ {
+ const uint32_t idx = (offset + ll) / 2;
+
+ int32_t result = _fn(_key, &data[idx * _stride]);
+
+ if (result < 0)
+ {
+ ll = idx;
+ }
+ else if (result > 0)
+ {
+ offset = idx + 1;
+ }
+ else
+ {
+ return idx;
+ }
+ }
+
+ return ~offset;
+ }
+
} // namespace bx