diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-27 10:36:22 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-27 10:36:22 +0000 |
commit | b88bb292821fd7742604ec4e280acebd9a049f62 (patch) | |
tree | 625e4e19e6619f7481e5a8103f876520950769f6 /src/contrib/ucw/binsearch.h | |
parent | Initial commit. (diff) | |
download | knot-b88bb292821fd7742604ec4e280acebd9a049f62.tar.xz knot-b88bb292821fd7742604ec4e280acebd9a049f62.zip |
Adding upstream version 3.0.5.upstream/3.0.5upstream
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; }) |