From 7068cd693f95253661ba9feb219831257b234b75 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sun, 2 Oct 2005 10:52:23 +0000 Subject: [PATCH] Added a library module for generic binary search. --- lib/binsearch.h | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+) create mode 100644 lib/binsearch.h diff --git a/lib/binsearch.h b/lib/binsearch.h new file mode 100644 index 00000000..67419563 --- /dev/null +++ b/lib/binsearch.h @@ -0,0 +1,26 @@ +/* + * UCW Library -- Generic Binary Search + * + * (c) 2005 Martin Mares + * + * This software may be freely distributed and used according to the terms + * of the GNU Lesser General Public License. + */ + +#define BIN_SEARCH_FIRST_GE_CMP(ary,N,x,ary_lt_x) ({ \ + uns l = 0, r = (N); \ + while (l < r) \ + { \ + uns m = (l+r)/2; \ + if (ary_lt_x(ary,m,x)) \ + l = m+1; \ + else \ + r = m; \ + } \ + l; \ +}) + +#define ARY_LT_NUM(ary,i,x) (ary)[i] < (x) + +#define BIN_SEARCH_FIRST_GE(ary,N,x) BIN_SEARCH_FIRST_GE_CMP(ary,N,x,ARY_LT_NUM) +#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; }) -- 2.39.2