lib/util/binsearch.h

   1 /*
   2    Unix SMB/CIFS implementation.
   3
   4    a generic binary search macro
   5
   6    Copyright (C) Andrew Tridgell 2009
   7
   8      ** NOTE! The following LGPL license applies to the binsearch.h
   9      ** header. This does NOT imply that all of Samba is released
  10      ** under the LGPL
  11
  12    This library is free software; you can redistribute it and/or
  13    modify it under the terms of the GNU Lesser General Public
  14    License as published by the Free Software Foundation; either
  15    version 3 of the License, or (at your option) any later version.
  16
  17    This library is distributed in the hope that it will be useful,
  18    but WITHOUT ANY WARRANTY; without even the implied warranty of
  19    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  20    Lesser General Public License for more details.
  21
  22    You should have received a copy of the GNU Lesser General Public
  23    License along with this library; if not, see <http://www.gnu.org/licenses/>.
  24 */
  25
  26 #ifndef _BINSEARCH_H
  27 #define _BINSEARCH_H
  28
  29 /* a binary array search, where the array is an array of pointers to structures,
  30    and we want to find a match for 'target' on 'field' in those structures.
  31
  32    Inputs:
  33       array:          base pointer to an array of structures
  34       arrray_size:    number of elements in the array
  35       field:          the name of the field in the structure we are keying off
  36       target:         the field value we are looking for
  37       comparison_fn:  the comparison function
  38       result:         where the result of the search is put
  39
  40    if the element is found, then 'result' is set to point to the found array element. If not,
  41    then 'result' is set to NULL.
  42
  43    The array is assumed to be sorted by the same comparison_fn as the
  44    search (with, for example, qsort)
  45  */
  46 #define BINARY_ARRAY_SEARCH_P(array, array_size, field, target, comparison_fn, result) do { \
  47         int32_t _b, _e; \
  48         (result) = NULL; \
  49         if (array_size) { for (_b = 0, _e = (array_size)-1; _b <= _e; ) { \
  50                 int32_t _i = (_b+_e)/2; \
  51                 int _r = comparison_fn(target, array[_i]->field); \
  52                 if (_r == 0) { (result) = array[_i]; break; } \
  53                 if (_r < 0) _e = _i - 1; else _b = _i + 1; \
  54         }} } while (0)
  55
  56 /*
  57   like BINARY_ARRAY_SEARCH_P, but assumes that the array is an array
  58   of structures, rather than pointers to structures
  59
  60   result points to the found structure, or NULL
  61  */
  62 #define BINARY_ARRAY_SEARCH(array, array_size, field, target, comparison_fn, result) do { \
  63         int32_t _b, _e; \
  64         (result) = NULL; \
  65         if (array_size) { for (_b = 0, _e = (array_size)-1; _b <= _e; ) {       \
  66                 int32_t _i = (_b+_e)/2; \
  67                 int _r = comparison_fn(target, array[_i].field); \
  68                 if (_r == 0) { (result) = &array[_i]; break; } \
  69                 if (_r < 0) _e = _i - 1; else _b = _i + 1; \
  70         }} } while (0)
  71
  72 /*
  73   like BINARY_ARRAY_SEARCH_P, but assumes that the array is an array
  74   of elements, rather than pointers to structures
  75
  76   result points to the found structure, or NULL
  77  */
  78 #define BINARY_ARRAY_SEARCH_V(array, array_size, target, comparison_fn, result) do { \
  79         int32_t _b, _e; \
  80         (result) = NULL; \
  81         if (array_size) { for (_b = 0, _e = (array_size)-1; _b <= _e; ) {       \
  82                 int32_t _i = (_b+_e)/2; \
  83                 int _r = comparison_fn(target, array[_i]); \
  84                 if (_r == 0) { (result) = &array[_i]; break; } \
  85                 if (_r < 0) _e = _i - 1; else _b = _i + 1; \
  86         }} } while (0)
  87
  88
  89 /*
  90   like BINARY_ARRAY_SEARCH_V, but if an exact result is not found, the 'next'
  91   argument will point to the element after the place where the exact result
  92   would have been. If an exact result is found, 'next' will be NULL. If the
  93   target is beyond the end of the list, both 'exact' and 'next' will be NULL.
  94   Unlike other binsearch macros, where there are several elements that compare
  95   the same, the exact result will always point to the first one.
  96
  97   If you don't care to distinguish between the 'greater than' and 'equals'
  98   cases, you can use the same pointer for both 'exact' and 'next'.
  99
 100   As with all the binsearch macros, the comparison function is always called
 101   with the search term first.
 102  */
 103 #define BINARY_ARRAY_SEARCH_GTE(array, array_size, target, comparison_fn, \
 104                                 exact, next) do {               \
 105         int32_t _b, _e;                                         \
 106         (exact) = NULL; (next) = NULL;                  \
 107         if ((array_size) > 0) {                                 \
 108                 for (_b = 0, _e = (array_size)-1; _b <= _e; ) { \
 109                         int32_t _i = (_b + _e) / 2;                     \
 110                         int _r = comparison_fn(target, &array[_i]); \
 111                         if (_r == 0) {                                  \
 112                                 (exact) = &array[_i];                   \
 113                                 _e = _i - 1;                            \
 114                         } else if (_r < 0) { _e = _i - 1;               \
 115                         } else  { _b = _i + 1; }                        \
 116                 }                                                       \
 117                 if ((exact) == NULL &&_b < (array_size)) {              \
 118                         (next) = &array[_b];                            \
 119         } } } while (0)
 120
 121 #endif