diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-05-06 00:53:35 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-05-06 00:53:35 +0000 |
commit | 69c6a41ffb878ef98c9378ed4b1634a404cfaa7f (patch) | |
tree | b2a4f704565d62fbb129ab9dc3b35977c50e6e7f /src/contrib/ucw/binsearch.h | |
parent | Initial commit. (diff) | |
download | knot-69c6a41ffb878ef98c9378ed4b1634a404cfaa7f.tar.xz knot-69c6a41ffb878ef98c9378ed4b1634a404cfaa7f.zip |
Adding upstream version 2.7.6.upstream/2.7.6upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to '')
-rw-r--r-- | src/contrib/ucw/binsearch.h | 50 |
1 files changed, 50 insertions, 0 deletions
diff --git a/src/contrib/ucw/binsearch.h b/src/contrib/ucw/binsearch.h new file mode 100644 index 0000000..b791d39 --- /dev/null +++ b/src/contrib/ucw/binsearch.h @@ -0,0 +1,50 @@ +/* + * UCW Library -- Generic Binary Search + * + * (c) 2005 Martin Mares <mj@ucw.cz> + * + * This software may be freely distributed and used according to the terms + * of the GNU Lesser General Public License. + */ + +#pragma once + +/*** + * [[defs]] + * Definitions + * ----------- + ***/ + +/** + * Find the first element not lower than \p x in the sorted array \p ary of \p N elements (non-decreasing order). + * Returns the index of the found element or \p N if no exists. Uses `ary_lt_x(ary,i,x)` to compare the i'th element with \p x. + * The time complexity is `O(log(N))`. + **/ +#define BIN_SEARCH_FIRST_GE_CMP(ary, N, ary_lt_x, x, ...) ({ \ + unsigned l = 0, r = (N); \ + while (l < r) \ + { \ + unsigned m = (l+r)/2; \ + if (ary_lt_x(ary, m, x, __VA_ARGS__)) \ + l = m+1; \ + else \ + r = m; \ + } \ + l; \ +}) + +/** + * The default comparison macro for \ref BIN_SEARCH_FIRST_GE_CMP(). + **/ +#define ARY_LT_NUM(ary,i,x) (ary)[i] < (x) + +/** + * Same as \ref BIN_SEARCH_FIRST_GE_CMP(), but uses the default `<` operator for comparisons. + **/ +#define BIN_SEARCH_FIRST_GE(ary,N,x) BIN_SEARCH_FIRST_GE_CMP(ary,N,ARY_LT_NUM,x) + +/** + * Search the sorted array \p ary of \p N elements (non-decreasing) for the first occurrence of \p x. + * Returns the index or -1 if no such element exists. Uses the `<` operator for comparisons. + **/ +#define BIN_SEARCH_EQ(ary,N,x) ({ int i = BIN_SEARCH_FIRST_GE(ary,N,x); if (i >= (N) || (ary)[i] != (x)) i=-1; i; }) |