Hi, This adds a method to binary search in a sorted array_slice.
The implementation is direct copy of vec:bsearch. Moreover, to only copy it once and not twice, I used const_cast in the non-const variants to be able to use the const variants. I hope that is acceptable abuse of const_cast but I'll be happy to change that if not. Bootstrapped and tested along code that actually uses it on x86_64-linux. OK for trunk? Thanks, Martin gcc/ChangeLog: 2022-08-08 Martin Jambor <mjam...@suse.cz> * vec.h (array_slice::bsearch): New methods. --- gcc/vec.h | 94 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 94 insertions(+) diff --git a/gcc/vec.h b/gcc/vec.h index b0477e1044c..61ebdc4ca13 100644 --- a/gcc/vec.h +++ b/gcc/vec.h @@ -2301,6 +2301,14 @@ public: // True if the array is valid, false if it is an array like INVALID. bool is_valid () const { return m_base || m_size == 0; } + /* Methods for binary search in sorted array_slice. */ + const T *bsearch (const void *key, int (*compar)(const void *, + const void *)) const; + T *bsearch (const void *key, int (*compar)(const void *, const void *)); + const T *bsearch (const void *key, + int (*compar)(const void *, const void *, void *), void *) const; + T *bsearch (const void *key, + int (*compar)(const void *, const void *, void *), void *); private: iterator m_base; unsigned int m_size; @@ -2361,6 +2369,92 @@ make_array_slice (T *base, unsigned int size) return array_slice<T> (base, size); } +/* Search the contents of the sorted array_slice with a binary search. CMP is + the comparison function to pass to bsearch. */ + +template<typename T> +inline const T * +array_slice<T>::bsearch (const void *key, + int (*compar) (const void *, const void *)) const +{ + const void *base = this->m_base; + size_t nmemb = this->size (); + size_t size = sizeof (T); + /* The following is a copy of glibc stdlib-bsearch.h. */ + size_t l, u, idx; + const void *p; + int comparison; + + l = 0; + u = nmemb; + while (l < u) + { + idx = (l + u) / 2; + p = (const void *) (((const char *) base) + (idx * size)); + comparison = (*compar) (key, p); + if (comparison < 0) + u = idx; + else if (comparison > 0) + l = idx + 1; + else + return (T *)const_cast<void *>(p); + } + + return NULL; +} + +template<typename T> +inline T * +array_slice<T>::bsearch (const void *key, + int (*compar) (const void *, const void *)) +{ + return const_cast<T>(bsearch (key, compar)); +} + +/* Search the contents of the sorted array_slice with a binary search. CMP is + the comparison function to pass to bsearch. */ + +template<typename T> +inline const T * +array_slice<T>::bsearch (const void *key, + int (*compar) (const void *, const void *, void *), + void *data) const +{ + const void *base = this->m_base; + size_t nmemb = this->size (); + size_t size = sizeof (T); + /* The following is a copy of glibc stdlib-bsearch.h. */ + size_t l, u, idx; + const void *p; + int comparison; + + l = 0; + u = nmemb; + while (l < u) + { + idx = (l + u) / 2; + p = (const void *) (((const char *) base) + (idx * size)); + comparison = (*compar) (key, p, data); + if (comparison < 0) + u = idx; + else if (comparison > 0) + l = idx + 1; + else + return (T *)const_cast<void *>(p); + } + + return NULL; +} + +template<typename T> +inline T * +array_slice<T>::bsearch (const void *key, + int (*compar) (const void *, const void *, void *), + void *data) +{ + return const_cast<T> (bsearch (key, compar, data)); +} + #if (GCC_VERSION >= 3000) # pragma GCC poison m_vec m_vecpfx m_vecdata #endif -- 2.37.2