diff options
author | 2023-01-05 15:32:40 +0100 | |
---|---|---|
committer | 2023-01-05 09:32:40 -0500 | |
commit | 812e6094f47bb8d1da5a6b421aa4c724cf2035c0 (patch) | |
tree | 0f5bab2fe9393d1f629e9bf63e76cecca74ec0c9 /3rdparty/bx/src/sort.cpp | |
parent | 4a1b41854bba8fc2567906b88bab8ca81e75d187 (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.cpp | 124 |
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 |