ucw/binsearch.h

   1 /*
   2  *      UCW Library -- Generic Binary Search
   3  *
   4  *      (c) 2005 Martin Mares <mj@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU Lesser General Public License.
   8  */
   9
  10 #define BIN_SEARCH_FIRST_GE_CMP(ary,N,x,ary_lt_x)  ({           \
  11   uns l = 0, r = (N);                                           \
  12   while (l < r)                                                 \
  13     {                                                           \
  14       uns m = (l+r)/2;                                          \
  15       if (ary_lt_x(ary,m,x))                                    \
  16         l = m+1;                                                \
  17       else                                                      \
  18         r = m;                                                  \
  19     }                                                           \
  20   l;                                                            \
  21 })
  22
  23 #define ARY_LT_NUM(ary,i,x) (ary)[i] < (x)
  24
  25 #define BIN_SEARCH_FIRST_GE(ary,N,x) BIN_SEARCH_FIRST_GE_CMP(ary,N,x,ARY_LT_NUM)
  26 #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; })