obt/bsearch.h

   1 /* -*- indent-tabs-mode: nil; tab-width: 4; c-basic-offset: 4; -*-
   2
   3    obt/bsearch.h for the Openbox window manager
   4    Copyright (c) 2010        Dana Jansens
   5
   6    This program is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2 of the License, or
   9    (at your option) any later version.
  10
  11    This program is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    See the COPYING file for a copy of the GNU General Public License.
  17 */
  18
  19 #ifndef __obt_bsearch_h
  20 #define __obt_bsearch_h
  21
  22 #include <glib.h>
  23
  24 G_BEGIN_DECLS
  25
  26 /*! Setup to do a binary search on an array. */
  27 #define BSEARCH_SETUP() \
  28     register guint l_BSEARCH, r_BSEARCH, out_BSEARCH; \
  29     register gboolean nearest_BSEARCH; (void)nearest_BSEARCH;
  30
  31 /*! Helper macro that just returns the input */
  32 #define BSEARCH_IS_T(t) (t)
  33
  34 /*! Search an array @ar holding elements of type @t, starting at index @start,
  35   with @size elements, looking for value @val. */
  36 #define BSEARCH(t, ar, start, size, val) \
  37     BSEARCH_CMP(t, ar, start, size, val, BSEARCH_IS_T)
  38
  39 /*! Search an array @ar, starting at index @start,
  40   with @size elements, looking for value @val of type @t,
  41   using the macro @to_t to convert values in the arrau @ar to type @t.
  42
  43   If all elements in @ar are less than @val, then BSEARCH_AT() will be
  44   the last element in @ar.
  45   If all elements in @ar are greater than @val, then BSEARCH_AT() will be
  46   the first element in @ar.
  47   Otherwise, if the element @val is not found then BSEARCH_AT() will be set to
  48   the position before the first element larger than @val.
  49 */
  50 #define BSEARCH_CMP(t, ar, start, size, val, to_t)  \
  51 do { \
  52     out_BSEARCH = (start); \
  53     l_BSEARCH = (size) > 0 ? (start) : (start + 1); \
  54     r_BSEARCH = (size) > 0 ? (start)+(size)-1 : (start); \
  55     nearest_BSEARCH = FALSE; \
  56     while (l_BSEARCH <= r_BSEARCH) { \
  57         /* m is in the middle, but to the left if there's an even number \
  58            of elements */ \
  59         out_BSEARCH = l_BSEARCH + (r_BSEARCH - l_BSEARCH)/2;      \
  60         if ((val) == to_t((ar)[out_BSEARCH])) {             \
  61             break; \
  62         } \
  63         else if ((val) < to_t((ar)[out_BSEARCH])) { \
  64             if (out_BSEARCH > start) { \
  65                 r_BSEARCH = out_BSEARCH-1; /* search to the left side */ \
  66             } else { \
  67                 /* reached the start of the array */ \
  68                 r_BSEARCH = out_BSEARCH; \
  69                 l_BSEARCH = out_BSEARCH + 1; \
  70             } \
  71         } \
  72         else { \
  73             l_BSEARCH = out_BSEARCH+1; /* search to the right side */ \
  74         } \
  75     } \
  76     if ((size) > 0 && (val) != to_t((ar)[out_BSEARCH])) { \
  77         if ((val) > to_t((ar)[out_BSEARCH])) { \
  78             nearest_BSEARCH = TRUE; \
  79         } \
  80         else if (out_BSEARCH > start) { \
  81             --out_BSEARCH; \
  82             nearest_BSEARCH = (val) > to_t((ar)[out_BSEARCH]); \
  83         } \
  84     } \
  85 } while (0)
  86
  87 /*! Returns true if the element last searched for was found in the array */
  88 #define BSEARCH_FOUND() (l_BSEARCH <= r_BSEARCH)
  89
  90 /*! Returns the position in the array at which the element last searched for
  91   was found. */
  92 #define BSEARCH_AT() (out_BSEARCH)
  93
  94 /*! Returns true if the element at BSEARCH_AT() in the array is the largest
  95   value in the array smaller than the search key. Returns false if there was
  96   nothing in the array smaller than the search key.
  97
  98   Should only be used when BSEARCH_FOUND() is false.
  99 */
 100 #define BSEARCH_FOUND_NEAREST_SMALLER() (!BSEARCH_FOUND() && nearest_BSEARCH)
 101
 102 G_END_DECLS
 103
 104 #endif