From a6fd06074da4720c77e83dca90d22c88a8dbe0b8 Mon Sep 17 00:00:00 2001 From: Eugene Sandulenko Date: Sun, 22 May 2016 22:58:38 +0200 Subject: COMMON: Fix SortedArray implementation. Had to use a modified bsearch for finding the nearest element. --- common/array.h | 24 +++++++++++++++++++++++- 1 file changed, 23 insertions(+), 1 deletion(-) diff --git a/common/array.h b/common/array.h index 320b367809..869d79b68b 100644 --- a/common/array.h +++ b/common/array.h @@ -378,7 +378,7 @@ public: * Inserts element at the sorted position. */ void insert(const T &element) { - T *where = (T *)bsearch(element, this->front(), this->_size, sizeof(T), _comparator); + T *where = (T *)bsearchMin(element, this->front(), this->_size, sizeof(T), _comparator); insert(where, element); } @@ -406,7 +406,29 @@ public: error("Operation not allowed with SortedArray"); } +private: + // Based on code Copyright (C) 2008-2009 Ksplice, Inc. + // Author: Tim Abbott + // Licensed under GPLv2+ + void *bsearchMin(const void *key, const void *base, uint num, uint size, + int (*cmp)(const void *key, const void *elt)) { + uint start = 0, end = num; + int result; + + while (start < end) { + uint mid = start + (end - start) / 2; + + result = cmp(key, (byte *)base + mid * size); + if (result < 0) + end = mid; + else if (result > 0) + start = mid + 1; + else + return (void *)((byte *)base + mid * size); + } + return (void *)((byte *)base + start * size); + } private: int (*_comparator)(const void *, const void *); -- cgit v1.2.3